×

A survey of the advances in the exploitation of the sparsity in the solution of large problems. (English) Zbl 0639.65020

The author gives an interesting survey and discussion on the advance made in recent years in the development of sparse matrix techniques [cf. D. J. Evans (ed.), Sparsity and its applications (1985; Zbl 0544.00021)]. One of the aims in using a sparse matrix technique to solve a large-scale problem involving sparse matrices is to reduce the storage space in the computer memory. The author describes the advantages and the limitations of two basic types of storage schemes, namely the static storage schemes and the dynamic storage schemes, for storing the elements of a sparse matrix in the computer memory, and gives in a systematic way the advances achieved after 1980 in the efforts to improve the performances of these storage schemes. The interested reader may greatly benefit from the large number of references included in the paper.
Reviewer: J.Parida

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis

Citations:

Zbl 0544.00021
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrei, N.; Rasturniou, C., Matrice rare si aplicatile lor (in Roumanian) (1983), Editura Technica: Editura Technica Bucuresti
[2] Axelsson, O., On preconditioned conjugate gradients methods, (Duff, I. S., Conjugate Gradient Methods and Similar Techniques. Conjugate Gradient Methods and Similar Techniques, Report No. R9636 (1979), A.E.R.E: A.E.R.E Harwell, England), 25-35
[3] Björck, Å., Iterative refinement of linear least squares solutions, I, BIT, 7, 257-278 (1967) · Zbl 0159.20404
[4] Björck, Å., Iterative refinement of linear least squares solutions, II, BIT, 8, 8-30 (1968) · Zbl 0177.43204
[5] Björck, Å., Methods for sparse linear least squares problems, (Bunch, J. R.; Rose, D. J., Sparse Matrix Computations (1976), Academic Press: Academic Press New York), 177-199 · Zbl 0734.65031
[6] Björck, Å., Comment on the iterative refinement of least-squares solutions, J. Amer. Statist. Assoc., 73, 161-166 (1978)
[7] Björck, Å., Numerical algorithms for linear least squares problems, (Report No. 2 (1978), Matematisk Institut, Universitetet i Trondheim: Matematisk Institut, Universitetet i Trondheim Trondheim, Norway) · Zbl 0734.65031
[8] Björck, A.; Duff, I. S., A direct method for the solution of sparse linear least squares problems, Ling. Alg. Appl., 34, 43-67 (1980) · Zbl 0471.65021
[9] Brayton, R. K.; Gustavson, F. G.; Willoughby, R. A., Some results on sparse matrices, Math. Comp., 24, 937-954 (1970) · Zbl 0233.65022
[10] Clasen, R. J., Techniques for automatic tolerance control in linear programming, Comm. ACM, 9, 802-803 (1966) · Zbl 0171.38302
[11] Cline, A. K.; Moler, C. B.; Stewart, G. W.; Wilkinson, J. H., An estimate for the condition number of a matrix, SIAM J. Numer. Anal., 16, 368-375 (1979) · Zbl 0403.65012
[12] Concus, P.; Golub, G. H.; Meurant, G., Block preconditioning for the conjugate gradient method, SIAM J. Sci. Statist. Comput., 6, 220-252 (1985) · Zbl 0556.65022
[13] Concus, P.; Golub, G. H.; O’Leary, D. P., A generalized conjugate gradient methods for the solution of elliptic partial differential equations, (Bunch, J. R.; Rose, D. J., Sparse Matrix Computations (1976), Academic Press: Academic Press New York), 309-332 · Zbl 0385.65048
[14] Cullum, J.; Willoughby, R. A., Computing eigenvectors (and eigenvalues) of large, symmetric matrices using Lanczos tridiagonalization, (Watson, G. A., Numerical Analysis Dundee. Numerical Analysis Dundee, Lecture Notes in Mathematics (1980), Springer: Springer Berlin), 46-63 · Zbl 0437.65028
[15] Curtis, A. R.; Reid, J. K., The solution of large sparse unsymmetric systems of linear equations, J. Inst. Math. Appl., 8, 344-353 (1971) · Zbl 0229.65032
[16] Dodson, D. S.; Lewis, J. G., Proposed sparse extensions to the basic linear algebra subprograms, ACM SIGNUM Newsletter, 20, 22-25 (1985)
[17] Dongarra, J. J.; Bunch, J. R.; Moler, C. B.; Stewart, G. W., LINPACK — Users’ Guide (1979), SIAM: SIAM Philadelphia · Zbl 0476.68025
[18] Dongarra, J. J.; Du Croz, J.; Hammarling, S.; Hanson, R. J., A proposal for an extended set of FORTRAN basic linear algebra subprograms, ACM SIGNUM Newsletter, 20, 2-18 (1985)
[19] Dongarra, J. J.; Leaf, G. K.; Minkoff, M., A preconditioned conjugate gradient method for solving a class of non-symmetric linear systems, (Report No. ANL-81-71 (1980), Argonne National Laboratory: Argonne National Laboratory Argonne, IL)
[20] Duff, I. S., Pivot selection and row ordering in Givens reduction of sparse matrices, Computing, 13, 239-248 (1974) · Zbl 0298.65029
[21] Duff, I. S., MA28—a set of FORTRAN subroutines for sparse unsymmetric linear equations, (Report No. R8730 (1977), A.E.R.E: A.E.R.E Harwell, England)
[22] Duff, I. S., MA32—a package for solving sparse unsymmetric systems using the frontal method, (Report No. R10079 (1981), A.E.R.E: A.E.R.E Harwell, England) · Zbl 0541.65017
[23] Duff, I. S., Parallel implementation of multifrontal schemes, (Report No. CSS174 (1985), A.E.R.E: A.E.R.E Harwell, England) · Zbl 0628.65018
[24] Duff, I. S., Data structures, algorithms and software for sparse matrices, (Evans, D. J., Sparsity and Applications (1985), Cambridge University Press: Cambridge University Press London), 1-29
[25] Duff, I. S.; Reid, J. K., A comparison of some methods for the solution of sparse overdetermined systems of linear equations, J. Inst. Math. Appl., 17, 267-280 (1976) · Zbl 0329.65026
[26] Duff, I. S.; Reid, J. K., Some design features of a sparse matrix code, ACM Trans. Math. Software, 5, 18-35 (1979) · Zbl 0401.65023
[27] Duff, I. S.; Reid, J. K., The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software, 9, 302-325 (1983) · Zbl 0515.65022
[28] Duff, I. S.; Reid, J. K., The multifrontal solution of unsymmetric sets of linear equations, SIAM J. Sci. Statist. Comput., 5, 633-641 (1984) · Zbl 0557.65017
[29] Eisenstat, S. C.; Gursky, M. C.; Schultz, M. H.; Sherman, A. H., The YALE sparse matrix package: I. The symmetric codes, Internat. J. Numer. Meth. Engng., 18, 1145-1151 (1982) · Zbl 0492.65012
[30] Eisenstat, S. C.; Gursky, M. C.; Schultz, M. H.; Sherman, A. H., The YALE sparse matrix package: II. The non-symmetric codes, (Report No. 114 (1977), Department of Computer Science, Yale University: Department of Computer Science, Yale University New Havens) · Zbl 0492.65012
[31] Evans, D. J., The use of preconditioning in iterative methods for solving linear equations with symmetric positive definite matrices, J. Inst. Math. Appl., 4, 295-314 (1968) · Zbl 0232.65031
[32] Evans, D. J., The analysis and application of sparse matrix algorithms in the finite element method, (Whiteman, J. R., The Mathematics of Finite Elements and Applications (1973), Academic Press: Academic Press London), 427-447
[33] Evans, D. J., Iterative sparse matrix algorithms, (Evans, D. J., Software for Numerical Mathematics (1974), Academic Press: Academic Press London), 49-83
[34] Evans, D. J., Iterative methods for sparse matrices, (Evans, D. J., Sparsity and its Applications (1985), Cambridge University Press: Cambridge University Press London), 45-111
[35] Gentleman, W. H., Least squares computations by Givens transformations without square roots, J. Inst. Math. Appl., 12, 329-336 (1973) · Zbl 0289.65020
[36] Gentleman, W. M., Error analysis of QR decompositions by Givens transformations, Lin. Alg. Appl., 10, 189-197 (1975) · Zbl 0308.65022
[37] Gentleman, W. M., Row elimination for solving sparse linear systems and least squares problems, (Numerical Analysis Dundee 1975. Numerical Analysis Dundee 1975, Lecture Notes in Mathematics, 506 (1976), Springer: Springer Berlin), 122-133
[38] George, J. A.; Heath, M. T., Solution of sparse linear least squares problems using Givens rotations, Lin. Alg. Appl., 34, 69-83 (1980) · Zbl 0459.65025
[39] George, J. A.; Heath, M. T.; Ng, E., A comparison of some methods for solving sparse linear least-squares problems, SIAM J. Sci. Statist. Comput., 4, 177-187 (1983) · Zbl 0532.65027
[40] George, J. A.; Heath, M. T.; Plemmons, R. J., Solution of large-scale sparse linear least squares problems using auxiliary storage, SIAM J. Sci. Statist. Comput., 2, 416-429 (1981) · Zbl 0469.65021
[41] George, J. A.; Liu, J. W., Computer Solution of Large Sparse Positive Definite Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0516.65010
[42] George, J. A.; Liu, J. W., Compact structural representation of sparse Cholesky, QR and LU factors, (Report No. CS-85-04 (1985), Department of Computer Science, York University: Department of Computer Science, York University Downsview, Ontario, Canada) · Zbl 0677.65022
[43] George, J. A.; Liu, J. W.; Ng, E., Row ordering schemes for sparse Givens transformations: I. Bipartite graph model, Lin. Alg. Appl., 61, 55-81 (1984) · Zbl 0557.65018
[44] George, J. A.; Liu, J. W.; Ng, E., Row ordering schemes for sparse Givens transformations: II. Implicit graph model, Lin. Alg. Appl., 75, 203-223 (1986) · Zbl 0596.65011
[45] George, J. A.; Liu, J. W.; Ng, E., Row ordering schemes for sparse Givens transformations: III. Analysis for a model problem, Lin. Alg. Appl., 75, 225-240 (1986) · Zbl 0596.65012
[46] George, J. A.; Liu, J. W.; Ng, E., A data structure for sparse QR and LU factors, (Report No. CS 85-16 (1985), Department of Computer Science, University of Waterloo: Department of Computer Science, University of Waterloo Ontario, Canada)
[47] George, J. A.; Ng, E., An implementation of Gaussian elimination with partial pivoting for sparse systems, SIAM J. Sci. Statist. Comput., 6, 390-406 (1985) · Zbl 0568.65017
[48] Givens, J. W., Numerical computation of characteristic values of a real symmetric matrix, (Report No. ORNL-1574 (1954), Oak Ridge National Laboratory: Oak Ridge National Laboratory Oak Ridge, Tennessee, USA) · Zbl 0055.35005
[49] Givens, J. W., Computation of plane unitary rotations transforming a general matrix to triangular form, J. Soc. Ind. Appl. Math., 6, 26-50 (1958) · Zbl 0087.11902
[50] G.H. Golub, P. Manneback and Ph. Toint, A comparison between some direct and iterative methods for large geodetic least squares problems, SIAM J. Sci. Statist. Comput.; G.H. Golub, P. Manneback and Ph. Toint, A comparison between some direct and iterative methods for large geodetic least squares problems, SIAM J. Sci. Statist. Comput.
[51] Grimes, R. G.; Lewis, J. G., Condition number estimation for sparse matrices, SIAM J. Sci. Statist. Comput., 2, 384-388 (1981) · Zbl 0469.65025
[52] Gustavson, F. G., Some basic techniques for solving sparse systems of linear equations, (Rose, D. J.; Willoughby, R. A., Sparse Matrices Applications (1972), Plenum Press: Plenum Press New York), 41-52
[53] Gustavson, F. G., Two fast algorithms for sparse matrices: multiplication and permuted transposition, ACM Trans. Math. Software, 4, 250-269 (1978) · Zbl 0384.65016
[54] Hammarling, S., A note on modifications to the Givens plane rotation, J. Inst. Math. Appl., 13, 215-218 (1974) · Zbl 0278.65037
[55] Harwell Subroutine Library Bulletin, (Duff, I. S., Changes to the MA28 suite (1983), A.E.R.E: A.E.R.E Harwell, England), 2
[56] Heath, M. T., Numerical methods for large sparse linear least squares problems, SIAM J. Statist. Comput., 5, 497-513 (1984) · Zbl 0575.65030
[57] Heath, M. T., Parallel Cholesky factorization in message-passing multiprocessor environments, (Report No. ORNL-6150 (1985), Oak Ridge National Laboratory: Oak Ridge National Laboratory Oak Ridge, Tennessee, USA)
[58] Ikramov, H. D., Sparse linear least-squares problems, (Gamkrelidze, R. V., Advances in Sciences an Technology: Mathematical Analysis, 23 (1985), Academy of Sciences of USSR: Academy of Sciences of USSR Moscow), 219-285 · Zbl 0638.65032
[59] Jennings, A.; Malik, G. M., Partial elimination, J. Inst. Math. Appl., 20, 307-316 (1977) · Zbl 0367.65019
[60] Lawson, C. L.; Hanson, R. J.; Kincaid, O. R.; Krogh, F. T., Basic linear algebra subprograms for Fortran usage, ACM Trans. Math. Software, 5, 308-323 (1979) · Zbl 0412.65022
[61] J.W.H. Liu, On general row merging for sparse Givens rotations, SIAM J. Sci. Statist. Comput.; J.W.H. Liu, On general row merging for sparse Givens rotations, SIAM J. Sci. Statist. Comput. · Zbl 0605.65031
[62] Liu, J. W.H., Computational models and task scheduling for parallel Cholesky factorization, (Report No. CS-85-01 (1985), Department of Computer Science, York University: Department of Computer Science, York University Downsview, Ontario, Canada), M3J 1P3
[63] Manneback, P., On some numerical methods for solving large sparse linear least squares problems, (Ph D Thesis (1985), Department of Mathematics, University of Namur: Department of Mathematics, University of Namur Namur, Belgium)
[64] Markowitz, H. M., The elimination form of the inverse and its applications to linear programming, Management Sci., 3, 255-267 (1957) · Zbl 0995.90592
[65] Munksgaard, N., Fortran subroutines for direct solution of sets of sparse and symmetric linear equations, (Report No. NI-77-05 (1977), Institute for Numerical Analysis, Technical University of Denmark: Institute for Numerical Analysis, Technical University of Denmark Lyngby, Denmark) · Zbl 0438.65035
[66] Munksgaard, N., Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients, ACM Trans. Math. Software, 6, 206-219 (1980) · Zbl 0438.65035
[67] Paige, C. C.; Saunders, M. A., LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8, 43-71 (1982) · Zbl 0478.65016
[68] Paige, C. C.; Saunders, M. A., Algorithm 583, LSQR: Sparse linear equations and least squares, ACM Trans. Math. Software, 8, 195-209 (1982)
[69] Parlett, B. N., The software scene in the extraction of eigenvalues from sparse matrices, SIAM J. Sci. Statist. Comput., 5, 590-604 (1984) · Zbl 0573.65025
[70] Penrose, R., A generalized inverse for matrices, Proc. Cambridge Phil. Soc., 51, 406-413 (1955) · Zbl 0065.24603
[71] Peters, F. J., Parallel pivoting algorithms for sparse symmetric matrices, Parallel Comput., 1, 99-110 (1984) · Zbl 0554.65017
[72] Pissanetzky, S., Sparse Matrix Technology (1984), Academic Press: Academic Press London · Zbl 0536.65019
[73] Reid, J. K., Fortran subroutines for handling sparse linear programming bases, (Report No. R8269 (1976), A.E.R.E: A.E.R.E Harwell, England)
[74] Reid, J. K., Solution of linear systems of equations: direct methods (general), (Barker, V. A., Sparse Matrix Techniques. Sparse Matrix Techniques, Lecture Notes in Mathematics, 572 (1977), Springer: Springer Berlin), 102-109
[75] Reid, J. K., Sparse matrices, (Jacobs, D. A.H., The State of the Art in Numerical Analysis (1977), Academic Press: Academic Press London), 85-146 · Zbl 0615.65049
[76] Reid, J. K., Tresolve, a Fortran package for solving set of linear finite-elements equations, (Report No. CSS 155 (1984), A.E.R.E: A.E.R.E Harwell, England)
[77] Rice, J. R.; Boisvert, R. F., Solving Elliptic Problems Using ELLPACK (1984), Springer: Springer New York · Zbl 0562.65064
[78] Ruhe, A., SOR methods for the eigenvalue problem with large sparse matrices, Math. Comp., 28, 695-710 (1974) · Zbl 0304.65027
[79] Ruhe, A., Implementation aspects of band Lanczos algorithms for computation of eigenvalues of large sparse symmetric matrices, Math. Comp., 33, 680-687 (1979) · Zbl 0443.65022
[80] Saad, Y., Variations of Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Lin. Alg. Appl., 34, 269-295 (1980) · Zbl 0456.65017
[81] Scott, D. S., Solving sparse symmetric generalized eigenvalue problems without factorization, SIAM J. Numer. Anal., 18, 102-110 (1981) · Zbl 0478.65023
[82] Tewarson, R. P., Sparse Matrices (1973), Academic Press: Academic Press New York · Zbl 0258.65035
[83] Ward, R. C.; Grey, L. J., Eigensystem computation for skew-symmetric and a class of symmetric matrices, ACM Trans. Math. Software, 4, 278-285 (1978) · Zbl 0384.65014
[84] Wolfe, P., Errors in the solution of linear programming problems, (Rall, L. B., Error in Digital Computation, 2 (1965), Wiley: Wiley New York) · Zbl 0173.17903
[85] Young, D. M.; Kincaid, D. R., The ITPACK package for large sparse linear systems, (Schiltz, M., Elliptic Problem Solvers (1981), Academic Press: Academic Press New York), 163-185 · Zbl 0467.65014
[86] Young, D. M.; Kincaid, D. R., The ITPACK software package, (Engquist, B.; Smadsaas, T., PDE Software: Modules, Interfaces and Systems (1984), North-Holland: North-Holland Amsterdam)
[87] Zlatev, Z., On some pivotal strategies in Gaussian elimination by sparse technique, SIAM J. Numer. Anal., 17, 18-30 (1980) · Zbl 0427.65016
[88] Zlatev, Z., On solving some large linear problems by direct methods, (Report No. DAIMI PB-111 (1980), Department of Computer Science, Aarhus University: Department of Computer Science, Aarhus University Aarhus, Denmark) · Zbl 0504.65043
[89] Zlatev, Z., Modified diagonally implicit Runge-Kutta methods, SIAM J. Sci. Statist. Comput., 2, 321-334 (1981) · Zbl 0475.65040
[90] Zlatev, Z., Use of iterative refinement in the solution of large sparse systems, SIAM J. Numer. Anal., 19, 381-399 (1982) · Zbl 0485.65022
[91] Zlatev, Z., Comparison of two pivotal strategies in sparse plane rotations, Comput. Math. Appl., 8, 119-135 (1982) · Zbl 0485.65031
[92] Zlatev, Z., General scheme for solving linear algebraic problems by direct methods, Appl. Numer. Math., 1, 177-186 (1985) · Zbl 0547.65035
[93] Zlatev, Z., Sparse matrix techniques for general matrices with real elements: pivotal strategies, decompositions and applications in ODE software, (Evans, D. J., Sparsity and its Applications (1985), Cambridge University Press: Cambridge University Press London), 185-227
[94] Zlatev, Z., Solving large systems of linear algebraic equations by the use of package Y12M, (Niku-Lari, A., Structural Analysis Systems, 2 (1985), Pergamon Press: Pergamon Press New York), 152-160
[95] Zlatev, Z.; Barker, V. A.; Thomson, P. G., SSLEST: a FORTRAN IV subroutine for solving sparse systems of linear equations (users’ guide), (Report NI-78-01 (1978), Institute for Numerical Analysis, Technical University of Denmark: Institute for Numerical Analysis, Technical University of Denmark Lyngby, Denmark)
[96] Zlatev, Z.; Nielsen, H. B., Preservation of sparsity in connection with iterative refinement, (Report No. NI-77-12 (1977), Institute for Numerical Analysis, Technical University of Denmark: Institute for Numerical Analysis, Technical University of Denmark Lyngby, Denmark)
[97] Zlatev, Z.; Nielsen, H. B., Least squares solution of large linear problems, (Höskuldsson, A.; Conradsen, K.; Jensen, B. Sloth; Esbensen, K., Symposium I Anvendt Statistik 1980 (1980), North Europe University Computing Centre: North Europe University Computing Centre Lyngby, Denmark), 17-52 · Zbl 0644.65028
[98] Zlatev, Z.; Nielsen, H. B., Solving large and sparse linear least-squares problems by conjugate gradients algorithms, (Report No. NI-86-06 (1986), Institute for Numerical Analysis, Technical University of Denmark: Institute for Numerical Analysis, Technical University of Denmark Lyngby, Denmark) · Zbl 0644.65028
[99] Zlatev, Z.; Schaumburg, K.; Wasniewski, J., Implementation of an iterative refinement option in a code for large and sparse systems, Comput. Chem., 4, 87-99 (1980)
[100] Zlatev, Z.; Thomson, P. G., ST—a FORTRAN IV subroutine for the solution of large systems of linear algebraic equations with real coefficients by use of sparse technique, (Report No. NI-76-05 (1976), Institute for Numerical Analysis, Technical University of Denmark: Institute for Numerical Analysis, Technical University of Denmark Lyngby, Denmark)
[101] Zlatev, Z.; Thomson, P. G., Sparse matrices-efficient decomposition and applications, (Duff, I. S., Sparse Matrices and Their Uses (1981), Academic Press: Academic Press London), 367-375
[102] Zlatev, Z.; Wasniewski, J., Package Y12M—solution of large and sparse systems of linear algebraic equations (1978), Mathematics Institute, University of Copenhagen: Mathematics Institute, University of Copenhagen Copenhagen, Preprint Ser., No. 24
[103] Zlatev, Z.; Wasniewski, J.; Schaumburg, K., Y12M—solution of large and sparse systems of linear algebraic equations, (Lecture Notes in Computer Science, 121 (1981), Springer: Springer Berlin) · Zbl 0461.65023
[104] Zlatev, Z.; Wasniewski, J.; Schaumburg, K., Comparison of two algorithms for solving large linear systems, SIAM J. Sci. Statist. Comput., 3, 486-501 (1982) · Zbl 0491.65017
[105] Zlatev, Z.; Wasniewski, J.; Schaumburg, K., Exploiting the sparsity in the solution of linear ordinary differential equations, Comput. Math. Appl., 11, 1069-1087 (1985) · Zbl 0576.65062
[106] Zlatev, Z.; Wasniewski, J.; Schaumburg, K., Numerical treatment of models arising in nuclear magnetic resonance spectroscopy, Advances Engng. Software, 8, 223-233 (1986)
[107] Zlatev, Z.; Wasniewski, J.; Schaumburg, K., Condition number estimators in a sparse matrix software, SIAM J. Sci. Statist. Comput., 7, 1175-1189 (1986) · Zbl 0594.65030
[108] Zmijewski, E.; Gilbert, J. R., A parallel algorithm for large sparse symbolic and numeric Cholesky factorization on a multiprocessor, (Report No. TR 86-733 (1986), Department of Computer Science, Cornell University: Department of Computer Science, Cornell University Ithaca, New York 14853, USA) · Zbl 0654.65025
[109] Østerby, O.; Zlatev, Z., Direct methods for sparse matrices, (Lecture Notes in Computer Science, 157 (1983), Springer: Springer Berlin) · Zbl 0516.65011
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.