Storing matrices on disk for efficient row and column retrieval. (English) Zbl 0575.68033
We study the problem of storing a matrix on disk where the cost for retrieving a row or column is the number of different pages containing elements of that row or column and the cost of a matrix is the sum of the cost for retrieving each row and column. We give a non-obvious, nontrivial lower bound on the cost and one algorithm that asymptotically achieves this bound if the page size is in a given set of integers, and another that achieves it if not.
MSC:
| 68N25 | Theory of operating systems |
References:
| [1] | McKellar, A. C.; Coffman, E. G., Organizing matrices and matrix operations for paged memory systems, Comm. ACM, 12, 153-165 (1969) · Zbl 0175.16405 |
| [2] | Moler, C. B., Matrix computation with Fortran and paging, Comm. ACM, 15, 268-270 (1972) |
| [3] | Fischer, P. C.; Probert, R. L., A note on matrix multiplication in a paging environment, (Proc. ACM National Conf. (1976)), 17-21 |
| [4] | Strassen, V., Gaussian elimination is not optimal, Numerische Mathematik, 13, 354-356 (1969) · Zbl 0185.40101 |
| [5] | Rosenberg, A. L., Preserving proximity in arrays, SIAM J. Comput., 4, 443-460 (1975) · Zbl 0324.68016 |
| [6] | DeMillo, R. A.; Eisenstat, S. C.; Lipton, R. E., Preserving average proximity in arrays, Comm. ACM, 21, 228-231 (1978) · Zbl 0378.68014 |
| [7] | Bollman, D., On preserving proximity in extended arrays, SIAM J. Comput., 5, 318-323 (1976) · Zbl 0332.68030 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
