Hostname: page-component-7b9c58cd5d-g9frx Total loading time: 0 Render date: 2025-03-15T05:08:39.596Z Has data issue: false hasContentIssue false
  • English
  • Français

A survey of direct methods for sparse linear systems

Published online by Cambridge University Press:  23 May 2016

Timothy A. Davis ,
Sivasankaran Rajamanickam  and
Wissam M. Sid-Lakhdar
Timothy A. Davis
Affiliation:
Department of Computer Science & Engineering, Texas A&M University, College Station, TX 77843-3112, USA E-mail: [email protected]
Sivasankaran Rajamanickam
Affiliation:
Center for Computing Research, Sandia National Laboratories, Albuquerque, NM 87185-1320, USA E-mail: [email protected]
Wissam M. Sid-Lakhdar
Affiliation:
Department of Computer Science & Engineering,Texas A&M University, College Station, TX 77843-3112, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Wilkinson defined a sparse matrix as one with enough zeros that it pays to take advantage of them.1 This informal yet practical definition captures the essence of the goal of direct methods for solving sparse matrix problems. They exploit the sparsity of a matrix to solve problems economically: much faster and using far less memory than if all the entries of a matrix were stored and took part in explicit computations. These methods form the backbone of a wide range of problems in computational science. A glimpse of the breadth of applications relying on sparse solvers can be seen in the origins of matrices in published matrix benchmark collections (Duff and Reid 1979a, Duff, Grimes and Lewis 1989a, Davis and Hu 2011). The goal of this survey article is to impart a working knowledge of the underlying theory and practice of sparse direct methods for solving linear systems and least-squares problems, and to provide an overview of the algorithms, data structures, and software available to solve these problems, so that the reader can both understand the methods and know how best to use them.

Type
Research Article
Information
Acta Numerica , Volume 25 , 01 May 2016 , pp. 383 - 566
Copyright
© Cambridge University Press, 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES4

Agrawal, A., Klein, P. and Ravi, R. (1993), Cutting down on fill using nested dissection: Provably good elimination orderings. In Graph Theory and Sparse Matrix Computation (George, A., Gilbert, J. R. and Liu, J. W. H., eds), Vol. 56 of IMA Volumes in Applied Mathematics, Springer, pp. 31–55.CrossRefGoogle Scholar
Agullo, E., Buttari, A., Guermouche, A. and Lopez, F. (2014), Implementing multifrontal sparse solvers for multicore architectures with sequential task flow runtime systems. Technical report IRI/RT2014-03FR, Institut de Recherche en Informatique de Toulouse (IRIT). To appear in ACM Trans. Math. Softw.Google Scholar
Agullo, E., Guermouche, A. and L’Excellent, J.-Y. (2008), ‘A parallel out-of-core multifrontal method: Storage of factors on disk and analysis of models for an out-of-core active memory’, Parallel Comput. 34, 296–317.CrossRefGoogle Scholar
Agullo, E., Guermouche, A. and L’Excellent, J.-Y. (2010), ‘Reducing the I/O volume in sparse out-of-core multifrontal methods’, SIAM J. Sci. Comput. 31, 4774–4794.CrossRefGoogle Scholar
Alaghband, G. (1989), ‘Parallel pivoting combined with parallel reduction and fill-in control’, Parallel Comput. 11, 201–221.CrossRefGoogle Scholar
Alaghband, G. (1995), ‘Parallel sparse matrix solution and performance’, Parallel Comput. 21, 1407–1430.CrossRefGoogle Scholar
Alaghband, G. and Jordan, H. F. (1989), ‘Sparse Gaussian elimination with controlled fill-in on a shared memory multiprocessor’, IEEE Trans. Comput. 38, 1539–1557.CrossRefGoogle Scholar
Alvarado, F. L. and Schreiber, R. (1993), ‘Optimal parallel solution of sparse triangular systems’, SIAM J. Sci. Comput. 14, 446–460.Google Scholar
Alvarado, F. L., Pothen, A. and Schreiber, R. (1993), Highly parallel sparse triangular solution. In Graph Theory and Sparse Matrix Computation (George, A., Gilbert, J. R. and Liu, J. W. H., eds), Vol. 56 of IMA Volumes in Applied Mathematics, Springer, pp. 141–158.CrossRefGoogle Scholar
Alvarado, F. L., Yu, D. C. and Betancourt, R. (1990), ‘Partitioned sparse $a^{-1}$ methods’, IEEE Trans. Power Systems 5, 452–459.CrossRefGoogle Scholar
Amestoy, P. R. and Duff, I. S. (1989), ‘Vectorization of a multiprocessor multifrontal code’, Intl J. Supercomp. Appl. 3, 41–59.Google Scholar
Amestoy, P. R. and Duff, I. S. (1993), ‘Memory management issues in sparse multifrontal methods on multiprocessors’, Intl J. Supercomp. Appl. 7, 64–82.Google Scholar
Amestoy, P. R. and Puglisi, C. (2002), ‘An unsymmetrized multifrontal LU factorization’, SIAM J. Matrix Anal. Appl. 24, 553–569.CrossRefGoogle Scholar
Amestoy, P. R., Ashcraft, C. C., Boiteau, O., Buttari, A., L’Excellent, J.-Y. and Weisbecker, C. (2015a), ‘Improving multifrontal methods by means of block low-rank representations’, SIAM J. Sci. Comput. 37, A1451–A1474.Google Scholar
Amestoy, P. R., Davis, T. A. and Duff, I. S. (1996a), ‘An approximate minimum degree ordering algorithm’, SIAM J. Matrix Anal. Appl. 17, 886–905.CrossRefGoogle Scholar
Amestoy, P. R., Davis, T. A. and Duff, I. S. (2004a), ‘Algorithm 837: AMD, an approximate minimum degree ordering algorithm’, ACM Trans. Math. Softw. 30, 381–388.CrossRefGoogle Scholar
Amestoy, P. R., Daydé, M. J. and Duff, I. S. (1989), Use of level-3 BLAS kernels in the solution of full and sparse linear equations. In High Performance Computing (Delhaye, J.-L. and Gelenbe, E., eds), North-Holland, pp. 19–31.Google Scholar
Amestoy, P. R., Duff, I. S. and L’Excellent, J.-Y. (2000), ‘Multifrontal parallel distributed symmetric and unsymmetric solvers’, Comput. Methods Appl. Mech. Eng. 184, 501–520.Google Scholar
Amestoy, P. R., Duff, I. S. and Puglisi, C. (1996b), ‘Multifrontal QR factorization in a multiprocessor environment’, Numer. Linear Algebra Appl. 3, 275–300.Google Scholar
Amestoy, P. R., Duff, I. S. and Vömel, C. (2004b), ‘Task scheduling in an asynchronous distributed memory multifrontal solver’, SIAM J. Matrix Anal. Appl. 26, 544–565.CrossRefGoogle Scholar
Amestoy, P. R., Duff, I. S., Guermouche, A. and Slavova, T. (2010), ‘Analysis of the solution phase of a parallel multifrontal solver’, Parallel Comput. 36, 3–15.CrossRefGoogle Scholar
Amestoy, P. R., Duff, I. S., L’Excellent, J.-Y. and Koster, J. (2001a), ‘A fully asynchronous multifrontal solver using distributed dynamic scheduling’, SIAM J. Matrix Anal. Appl. 23, 15–41.Google Scholar
Amestoy, P. R., Duff, I. S., L’Excellent, J.-Y. and Li, X. S. (2001b), ‘Analysis and comparison of two general sparse solvers for distributed memory computers’, ACM Trans. Math. Softw. 27, 388–421.CrossRefGoogle Scholar
Amestoy, P. R., Duff, I. S., L’Excellent, J.-Y. and Li, X. S. (2003a), ‘Impact of the implementation of MPI point-to-point communications on the performance of two general sparse solvers’, Parallel Comput. 29, 833–947.Google Scholar
. Amestoy, P. R., Duff, I. S., L’Excellent, J.-Y. and Rouet, F. H. (2015b), ‘Parallel computation of entries of $A^{-1}$’, SIAM J. Sci. Comput. 37, C268–C284.CrossRefGoogle Scholar
Amestoy, P. R., Duff, I. S., L’Excellent, J.-Y., Robert, Y., Rouet, F. H. and Uçar, B. (2012), ‘On computing inverse entries of a sparse matrix in an out-of-core environment’, SIAM J. Sci. Comput. 34, 1975–1999.CrossRefGoogle Scholar
Amestoy, P. R., Duff, I. S., Pralet, S. and Vömel, C. (2003b), ‘Adapting a parallel sparse direct solver to architectures with clusters of SMPs’, Parallel Comput. 29, 1645–1668.CrossRefGoogle Scholar
Amestoy, P. R., Guermouche, A., L’Excellent, J.-Y. and Pralet, S. (2006), ‘Hybrid scheduling for the parallel solution of linear systems’, Parallel Comput. 32, 136–156.CrossRefGoogle Scholar
Amestoy, P. R., L’Excellent, J.-Y. and Sid-Lakhdar, W. M. (2014a), Characterizing asynchronous broadcast trees for multifrontal factorizations. In Proc. SIAM Workshop on Combinatorial Scientific Computing: CSC14, pp. 51–53.Google Scholar
Amestoy, P. R., L’Excellent, J.-Y., Rouet, F.-H. and Sid-Lakhdar, W. M. (2014b), Modeling 1D distributed-memory dense kernels for an asynchronous multifrontal sparse solver. In Proc. High-Performance Computing for Computational Science: VECPAR 2014.Google Scholar
Amestoy, P. R., Li, X. S. and Ng, E. (2007a), ‘Diagonal Markowitz scheme with local symmetrization’, SIAM J. Matrix Anal. Appl. 29, 228–244.CrossRefGoogle Scholar
Amestoy, P. R., Li, X. S. and Pralet, S. (2007b), ‘Unsymmetric ordering using a constrained Markowitz scheme’, SIAM J. Matrix Anal. Appl. 29, 302–327.CrossRefGoogle Scholar
Amit, R. and Hall, C. (1981), ‘Storage requirements for profile and frontal elimination’, SIAM J. Numer. Anal. 19, 205–218.CrossRefGoogle Scholar
Anderson, E. and Saad, Y. (1989), ‘Solving sparse triangular linear systems on parallel computers’, Intl J. High Speed Computing 1, 73–95.Google Scholar
Anderson, E., Bai, Z., Bischof, C. H., Blackford, S., Demmel, J. W., Dongarra, J. J., Du Croz, J., Greenbaum, A., Hammarling, S., Mckenney, A. and Sorensen, D. C. (1999), LAPACK Users’ Guide, third edition, SIAM. www.netlib.org/lapack/lug/Google Scholar
Arioli, M., Demmel, J. W. and Duff, I. S. (1989a), ‘Solving sparse linear systems with sparse backward error’, SIAM J. Matrix Anal. Appl. 10, 165–190.Google Scholar
Arioli, M., Duff, I. S. and de Rijk, P. P. M. (1989b), ‘On the augmented systems approach to sparse least-squares problems’, Numer. Math. 55, 667–684.CrossRefGoogle Scholar
Arioli, M., Duff, I. S., Gould, N. I. M. and Reid, J. K. (1990), ‘Use of the P4 and P5 algorithms for in-core factorization of sparse matrices’, SIAM J. Sci. Comput. 11, 913–927.Google Scholar
Arnold, C. P., Parr, M. I. and Dewe, M. B. (1983), ‘An efficient parallel algorithm for the solution of large sparse linear matrix equations’, IEEE Trans. Comput. C‐32, 265–272.CrossRefGoogle Scholar
Ashcraft, C. C. (1987), A vector implementation of the multifrontal method for large sparse, symmetric positive definite systems. Technical report ETA-TR-51, Boeing Computer Services, Seattle, WA.Google Scholar
Ashcraft, C. C. (1993), The fan-both family of column-based distributed Cholesky factorization algorithms. In Graph Theory and Sparse Matrix Computation (George, A., Gilbert, J. R. and Liu, J. W. H., eds), Vol. 56 of IMA Volumes in Applied Mathematics, Springer, pp. 159–190.Google Scholar
Ashcraft, C. C. (1995), ‘Compressed graphs and the minimum degree algorithm’, SIAM J. Sci. Comput. 16, 1404–1411.Google Scholar
Ashcraft, C. C. and Grimes, R. G. (1989), ‘The influence of relaxed supernode partitions on the multifrontal method’, ACM Trans. Math. Softw. 15, 291–309.CrossRefGoogle Scholar
Ashcraft, C. C. and Grimes, R. G. (1999), SPOOLES: An object-oriented sparse matrix library. In Proc. 1999 SIAM Conference on Parallel Processing for Scientific Computing. www.netlib.org/linalg/spoolesGoogle Scholar
Ashcraft, C. C. and Liu, J. W. H. (1997), ‘Using domain decomposition to find graph bisectors’, BIT Numer. Math. 37, 506–534.CrossRefGoogle Scholar
Ashcraft, C. C. and Liu, J. W. H. (1998a), ‘Applications of the Dulmage–Mendelsohn decomposition and network flow to graph bisection improvement’, SIAM J. Matrix Anal. Appl. 19, 325–354.Google Scholar
Ashcraft, C. C. and Liu, J. W. H. (1998b), ‘Robust ordering of sparse matrices using multisection’, SIAM J. Matrix Anal. Appl. 19, 816–832.Google Scholar
Ashcraft, C. C., Eisenstat, S. C. and Liu, J. W. H. (1990a), ‘A fan-in algorithm for distributed sparse numerical factorization’, SIAM J. Sci. Comput. 11, 593–599.Google Scholar
Ashcraft, C. C., Eisenstat, S. C., Liu, J. W. H. and Sherman, A. H. (1990b), A comparison of three column-based distributed sparse factorization schemes. Technical report YALEU/DCS/RR-810, Yale University.Google Scholar
Ashcraft, C. C., Grimes, R. G. and Lewis, J. G. (1998), ‘Accurate symmetric indefinite linear equation solvers’, SIAM J. Matrix Anal. Appl. 20, 513–561.Google Scholar
Ashcraft, C. C., Grimes, R. G., Lewis, J. G., Peyton, B. W. and Simon, H. D. (1987), ‘Progress in sparse matrix methods for large linear systems on vector supercomputers’, Intl J. Supercomp. Appl. 1, 10–30.Google Scholar
Avron, H., Shklarski, G. and Toledo, S. (2008), ‘Parallel unsymmetric-pattern multifrontal sparse LU with column preordering’, ACM Trans. Math. Softw. 34, 1–31.CrossRefGoogle Scholar
Aykanat, C., Cambazoglu, B. B. and Uçar, B. (2008), ‘Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices’, J. Parallel Distrib. Comput. 68, 609–625.CrossRefGoogle Scholar
Aykanat, C., Pinar, A. and Çatalyürek, U. V. (2004), ‘Permuting sparse rectangular matrices into block-diagonal form’, SIAM J. Sci. Comput. 25, 1860–1879.Google Scholar
Azad, A., Halappanavar, M., Rajamanickam, S., Boman, E., Khan, A. and Pothen, A. (2012), Multithreaded algorithms for maximum matching in bipartite graphs. In Proc. 26th IEEE International Parallel and Distributed Processing Symposium: IPDPS, pp. 860–872.Google Scholar
Bank, R. E. and Rose, D. J. (1990), ‘On the complexity of sparse Gaussian elimination via bordering’, SIAM J. Sci. Comput. 11, 145–160.Google Scholar
Bank, R. E. and Smith, R. K. (1987), ‘General sparse elimination requires no permanent integer storage’, SIAM J. Sci. Comput. 8, 574–584.Google Scholar
Barnard, S. T., Pothen, A. and Simon, H. D. (1995), ‘A spectral algorithm for envelope reduction of sparse matrices’, Numer. Linear Algebra Appl. 2, 317–334.Google Scholar
Benner, R. E., Montry, G. R. and Weigand, G. G. (1987), ‘Concurrent multifrontal methods: Shared memory, cache, and frontwidth issues’, Intl J. Supercomp. Appl. 1, 26–44.Google Scholar
Berge, C. (1957), ‘Two theorems in graph theory’, Proc. Nat. Acad. Sci. USA 43, 842.Google Scholar
Berman, P. and Schnitger, G. (1990), ‘On the performance of the minimum degree ordering for Gaussian elimination’, SIAM J. Matrix Anal. Appl. 11, 83–88.Google Scholar
Berry, A., Dahlhaus, E., Heggernes, P. and Simonet, G. (2008), ‘Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree’, Theoret. Comput. Sci. 409, 601–616.Google Scholar
Berry, R. D. (1971), ‘An optimal ordering of electronic circuit equations for a sparse matrix solution’, IEEE Trans. Circuit Theory CT‐19, 40–50.CrossRefGoogle Scholar
Bhat, M. V., Habashi, W. G., Liu, J. W. H., Nguyen, V. N. and Peeters, M. F. (1993), ‘A note on nested dissection for rectangular grids’, SIAM J. Matrix Anal. Appl. 14, 253–258.Google Scholar
Birkhoff, G. and George, A. (1973), Elimination by nested dissection. In Complexity of Sequential and Parallel Numerical Algorithms (Traub, J. F., ed.), Academic, pp. 221–269.Google Scholar
Bischof, C. H. and Hansen, P. C. (1991), ‘Structure-preserving and rank-revealing QR-factorizations’, SIAM J. Sci. Comput. 12, 1332–1350.CrossRefGoogle Scholar
Bischof, C. H., Lewis, J. G. and Pierce, D. J. (1990), ‘Incremental condition estimation for sparse matrices’, SIAM J. Matrix Anal. Appl. 11, 644–659.CrossRefGoogle Scholar
Björck, A. (1984), ‘A general updating algorithm for constrained linear least squares problems’, SIAM J. Sci. Comput. 5, 394–402.CrossRefGoogle Scholar
Björck, A. (1988), ‘A direct method for sparse least squares problems with lower and upper bounds’, Numer. Math. 54, 19–32.Google Scholar
Björck, A. (1996), Numerical Methods for Least Squares Problems, SIAM.Google Scholar
Björck, A. and Duff, I. S. (1988), ‘A direct method for sparse linear least squares problems’, Linear Algebra Appl. 34, 43–67.CrossRefGoogle Scholar
Bjorstad, P. E. (1987), ‘A large scale, sparse, secondary storage, direct linear equation solver for structural analysis and its implementation on vector and parallel architectures’, Parallel Comput. 5, 3–12.Google Scholar
Blackford, L., Choi, J., Cleary, A., D’Azevedo, E., Demmel, J., Dhillon, I., Dongarra, J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D. and Whaley, R. (1997), ScaLAPACK Users’ Guide, SIAM.Google Scholar
Boman, E. G. and Hendrickson, B. (1996), A multilevel algorithm for reducing the envelope of sparse matrices. Technical report SCCM-96-14, Stanford University.Google Scholar
Boman, E. G., Çatalyürek, Ü. V., Chevalier, C. and Devine, K. D. (2012), ‘The Zoltan and Isorropia parallel toolkits for combinatorial scientific computing: Partitioning, ordering and coloring’, Sci. Program. 20, 129–150.Google Scholar
Brainman, I. and Toledo, S. (2002), ‘Nested-dissection orderings for sparse LU with partial pivoting’, SIAM J. Matrix Anal. Appl. 23, 998–1012.Google Scholar
Brayton, R. K., Gustavson, F. G. and Willoughby, R. A. (1970), ‘Some results on sparse matrices’, Math. Comp. 24(112), 937–954.CrossRefGoogle Scholar
Brown, N. G. and Wait, R. (1981), A branching envelope reducing algorithm for finite element meshes. In Sparse Matrices and their Uses (Duff, I. S., ed.), Academic, pp. 315–324.Google Scholar
Bui, T. and Jones, C. (1993), A heuristic for reducing fill in sparse matrix factorization. In Proc. 6th SIAM Conference on Parallel Processing for Scientific Computation, SIAM, pp. 445–452.Google Scholar
Bunch, J. R. (1973), Complexity of sparse elimination. In Complexity of Sequential and Parallel Numerical Algorithms (Traub, J. F., ed.), Academic, pp. 197–220.Google Scholar
Bunch, J. R. (1974), ‘Partial pivoting strategies for symmetric matrices’, SIAM J. Numer. Anal. 11, 521–528.Google Scholar
Bunch, J. R. and Kaufman, L. (1977), ‘Some stable methods for calculating inertia and solving symmetric linear systems’, Math. Comp. 31, 163–179.Google Scholar
Buttari, A. (2013), ‘Fine-grained multithreading for the multifrontal QR factorization of sparse matrices’, SIAM J. Sci. Comput. 35, C323–C345.Google Scholar
Bykat, A. (1977), ‘A note on an element ordering scheme’, Intl J. Numer. Methods Eng. 11, 194–198.Google Scholar
Calahan, D. A. (1973), Parallel solution of sparse simultaneous linear equations. In Proc. 11th Annual Allerton Conference on Circuits and System Theory, pp. 729–735.Google Scholar
Cardenal, J., Duff, I. S. and Jiménez, J. (1998), ‘Solution of sparse quasi-square rectangular systems by Gaussian elimination’, IMA J. Numer. Anal. 18, 165–177.Google Scholar
Çatalyürek, U. V. and Aykanat, C. (1999), ‘Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication’, IEEE Trans. Parallel Distrib. Systems 10, 673–693.Google Scholar
Çatalyürek, U. V. and Aykanat, C. (2001), A fine-grain hypergraph model for 2D decomposition of sparse matrices. In Proc. 15th IEEE International Parallel and Distributed Processing Symposium: IPDPS ’01, pp. 1199–1204.Google Scholar
Çatalyürek, U. V. and Aykanat, C. (2011), PaToH: Partitioning tool for hypergraphs. http://bmi.osu.edu/umit/software.htmlGoogle Scholar
Çatalyürek, U. V., Aykanat, C. and Kayaaslan, E. (2011), ‘Hypergraph partitioning-based fill-reducing ordering for symmetric matrices’, SIAM J. Sci. Comput. 33, 1996–2023.CrossRefGoogle Scholar
Chan, W. M. and George, A. (1980), ‘A linear time implementation of the reverse Cuthill–McKee algorithm’, BIT Numer. Math. 20, 8–14.Google Scholar
Chen, G., Malkowski, K., Kandemir, M. and Raghavan, P. (2005), Reducing power with performance constraints for parallel sparse applications. In Proc. 19th IEEE Parallel and Distributed Processing Symposium.Google Scholar
Chen, Y., Davis, T. A., Hager, W. W. and Rajamanickam, S. (2008), ‘Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate’, ACM Trans. Math. Softw. 35, 1–14.Google Scholar
Chen, Y. T. and Tewarson, R. P. (1972a), ‘On the fill-in when sparse vectors are orthonormalized’, Computing 9, 53–56.Google Scholar
Chen, Y. T. and Tewarson, R. P. (1972b), ‘On the optimal choice of pivots for the Gaussian elimination’, Computing 9, 245–250.Google Scholar
Chen, X., Ren, L., Wang, Y. and Yang, H. (2015), ‘GPU-accelerated sparse LU factorization for circuit simulation with performance modeling’, IEEE Trans. Parallel Distrib. Systems 26, 786–795.CrossRefGoogle Scholar
Chen, X., Wang, Y. and Yang, H. (2013), ‘NICSLU: an adaptive sparse matrix solver for parallel circuit simulation’, IEEE Trans. Computer-Aided Design Integ. Circ. Sys. 32, 261–274.Google Scholar
Cheng, K. Y. (1973a), ‘Minimizing the bandwidth of sparse symmetric matrices’, Computing 11, 103–110.Google Scholar
Cheng, K. Y. (1973b), ‘Note on minimizing the bandwidth of sparse, symmetric matrices’, Computing 11, 27–30.Google Scholar
Chevalier, C. and Pellegrini, F. (2008), ‘PT-SCOTCH: A tool for efficient parallel graph ordering’, Parallel Comput. 34, 318–331.Google Scholar
Chu, E. and George, A. (1990), ‘Sparse orthogonal decomposition on a hypercube multiprocessor’, SIAM J. Matrix Anal. Appl. 11, 453–465.CrossRefGoogle Scholar
Chu, E., George, A., Liu, J. W. H. and Ng, E. G. (1984), SPARSPAK: Waterloo sparse matrix package, user’s guide for SPARSPAK-A. Technical report CS-84-36, Department of Computer Science, University of Waterloo, Ontario. https://cs.uwaterloo.ca/research/tr/1984/CS-84-36.pdfGoogle Scholar
Cliffe, K. A., Duff, I. S. and Scott, J. A. (1998), ‘Performance issues for frontal schemes on a cache-based high-performance computer’, Intl J. Numer. Methods Eng. 42, 127–143.3.0.CO;2-K>CrossRefGoogle Scholar
Coleman, T. F., Edenbrandt, A. and Gilbert, J. R. (1986), ‘Predicting fill for sparse orthogonal factorization’, J. Assoc. Comput. Mach. 33, 517–532.Google Scholar
Collins, R. J. (1973), ‘Bandwidth reduction by automatic renumbering’, Intl J. Numer. Methods Eng. 6, 345–356.Google Scholar
Conroy, J. M. (1990), ‘Parallel nested dissection’, Parallel Comput. 16, 139–156.CrossRefGoogle Scholar
Conroy, J. M., Kratzer, S. G., Lucas, R. F. and Naiman, A. E. (1998), ‘Data-parallel sparse LU factorization’, SIAM J. Sci. Comput. 19, 584–604.Google Scholar
Cormen, T. H., Leiserson, C. E. and Rivest, R. L. (1990), Introduction to Algorithms, MIT Press.Google Scholar
Cozette, O., Guermouche, A. and Utard, G. (2004), Adaptive paging for a multifrontal solver. In Proc. 18th International Conference on Supercomputing, ACM, pp. 267–276.Google Scholar
Crane, H. L., Gibbs, N. E., Poole, W. G. and Stockmeyer, P. K. (1976), ‘Algorithm 508: Matrix bandwidth and profile reduction’, ACM Trans. Math. Softw. 2, 375–377.CrossRefGoogle Scholar
Curtis, A. R. and Reid, J. K. (1971), ‘The solution of large sparse unsymmetric systems of linear equations’, IMA J. Appl. Math. 8, 344–353.Google Scholar
Cuthill, E. (1972), Several strategies for reducing the bandwidth of matrices. In Sparse Matrices and their Applications (Rose, D. J. and Willoughby, R. A., eds), Plenum, pp. 157–166.Google Scholar
Cuthill, E. and Mckee, J. (1969), Reducing the bandwidth of sparse symmetric matrices. In Proc. 24th Conference of the ACM, Brandon Press, pp. 157–172.Google Scholar
Damhaug, A. C. and Reid, J. R. (1996), MA46: A Fortran code for direct solution of sparse unsymmetric linear systems of equations from finite-element applications. Technical report RAL-TR-96-010, Rutherford Appleton Laboratory, Harwell, UK.Google Scholar
Dave, A. K. and Duff, I. S. (1987), ‘Sparse matrix calculations on the CRAY-2’, Parallel Comput. 5, 55–64.Google Scholar
Davis, T. A. (2004a), ‘Algorithm 832: UMFPACK V4.3, an unsymmetric-pattern multifrontal method’, ACM Trans. Math. Softw. 30, 196–199.Google Scholar
Davis, T. A. (2004b), ‘A column pre-ordering strategy for the unsymmetric-pattern multifrontal method’, ACM Trans. Math. Softw. 30, 165–195.Google Scholar
Davis, T. A. (2005), ‘Algorithm 849: A concise sparse Cholesky factorization package’, ACM Trans. Math. Softw. 31, 587–591.Google Scholar
Davis, T. A. (2006), Direct Methods for Sparse Linear Systems, SIAM.Google Scholar
Davis, T. A. (2011a), ‘Algorithm 915: SuiteSparseQR, multifrontal multithreaded rank-revealing sparse QR factorization’, ACM Trans. Math. Softw. 38, 8:1–8:22.Google Scholar
Davis, T. A. (2011b), MATLAB Primer, eighth edition, Chapman & Hall/CRC.Google Scholar
Davis, T. A. (2013), ‘Algorithm 930: FACTORIZE, an object-oriented linear system solver for MATLAB’, ACM Trans. Math. Softw. 39, 28:1–28:18.Google Scholar
Davis, T. A. and Davidson, E. S. (1988), ‘Pairwise reduction for the direct, parallel solution of sparse unsymmetric sets of linear equations’, IEEE Trans. Comput. 37, 1648–1654.Google Scholar
Davis, T. A. and Duff, I. S. (1997), ‘An unsymmetric-pattern multifrontal method for sparse LU factorization’, SIAM J. Matrix Anal. Appl. 18, 140–158.Google Scholar
Davis, T. A. and Duff, I. S. (1999), ‘A combined unifrontal/multifrontal method for unsymmetric sparse matrices’, ACM Trans. Math. Softw. 25, 1–20.Google Scholar
Davis, T. A. and Hager, W. W. (1999), ‘Modifying a sparse Cholesky factorization’, SIAM J. Matrix Anal. Appl. 20, 606–627.Google Scholar
Davis, T. A. and Hager, W. W. (2001), ‘Multiple-rank modifications of a sparse Cholesky factorization’, SIAM J. Matrix Anal. Appl. 22, 997–1013.Google Scholar
Davis, T. A. and Hager, W. W. (2005), ‘Row modifications of a sparse Cholesky factorization’, SIAM J. Matrix Anal. Appl. 26, 621–639.Google Scholar
Davis, T. A. and Hager, W. W. (2009), ‘Dynamic supernodes in sparse Cholesky update/downdate and triangular solves’, ACM Trans. Math. Softw. 35, 1–23.CrossRefGoogle Scholar
Davis, T. A. and Hu, Y. (2011), ‘The University of Florida sparse matrix collection’, ACM Trans. Math. Softw. 38, 1:1–1:25.Google Scholar
Davis, T. A. and Palamadai Natarajan, E. (2010), ‘Algorithm 907: KLU, a direct sparse solver for circuit simulation problems’, ACM Trans. Math. Softw. 37, 36:1–36:17.Google Scholar
Davis, T. A. and Yew, P. C. (1990), ‘A nondeterministic parallel algorithm for general unsymmetric sparse LU factorization’, SIAM J. Matrix Anal. Appl. 11, 383–402.Google Scholar
Davis, T. A., Gilbert, J. R., Larimore, S. I. and Ng, E. G. (2004a), ‘Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm’, ACM Trans. Math. Softw. 30, 377–380.Google Scholar
Davis, T. A., Gilbert, J. R., Larimore, S. I. and Ng, E. G. (2004b), ‘A column approximate minimum degree ordering algorithm’, ACM Trans. Math. Softw. 30, 353–376.Google Scholar
Daydé, M. J. and Duff, I. S. (1997), The use of computational kernels in full and sparse linear solvers, efficient code design on high-performance RISC processors. In Vector and Parallel Processing: VECPAR’96 (Palma, J. M. L. M. and Dongarra, J., eds), Vol. 1215 of Lecture Notes in Computer Science, Springer, pp. 108–139.Google Scholar
De Souza, C., Keunings, R., Wolsey, L. A. and Zone, O. (1994), ‘A new approach to minimising the frontwidth in finite element calculations’, Comput. Methods Appl. Mech. Eng. 111, 323–334.Google Scholar
Del Corso, G. M. and Manzini, G. (1999), ‘Finding exact solutions to the bandwidth minimization problem’, Computing 62, 189–203.Google Scholar
Dembart, B. and Neves, K. W. (1977), Sparse triangular factorization on vector computers. In Exploring Applications of Parallel Processing to Power Systems Applications (Anderson, P. M., ed.), Electric Power Research Institute, California, pp. 57–101.Google Scholar
Demmel, J. W. (1997), Applied Numerical Linear Algebra, SIAM.Google Scholar
Demmel, J. W., Eisenstat, S. C., Gilbert, J. R., Li, X. S. and Liu, J. W. H. (1999a), ‘A supernodal approach to sparse partial pivoting’, SIAM J. Matrix Anal. Appl. 20, 720–755.Google Scholar
Demmel, J. W., Gilbert, J. R. and Li, X. S. (1999b), ‘An asynchronous parallel supernodal algorithm for sparse Gaussian elimination’, SIAM J. Matrix Anal. Appl. 20, 915–952.Google Scholar
Devine, K. D., Boman, E. G., Heaphy, R. T., Bisseling, R. H. and Çatalyürek, U. V. (2006), Parallel hypergraph partitioning for scientific computing. In Proc. 20th IEEE International Parallel and Distributed Processing Symposium: IPDPS’06.Google Scholar
Dobrian, F. and Pothen, A. (2005), Oblio: Design and performance. In State of the Art in Scientific Computing (Dongarra, J., Madsen, K. and Wasniewski, J., eds), Vol. 3732 of Lecture Notes in Computer Science, Springer, pp. 758–767.Google Scholar
Dobrian, F., Kumfert, G. K. and Pothen, A. (2000), The design of sparse direct solvers using object oriented techniques. In Advances in Software Tools for Scientific Computing (Bruaset, A. M., Langtangen, H. P. and Quak, E., eds), Springer, pp. 89–131.Google Scholar
Dongarra, J. J., Du Croz, J., Duff, I. S. and Hammarling, S. (1990), ‘A set of level-3 basic linear algebra subprograms’, ACM Trans. Math. Softw. 16, 1–17.Google Scholar
Dongarra, J. J., Duff, I. S., Sorensen, D. C. and Van der Vorst, H. A. (1998), Numerical Linear Algebra for High-Performance Computers, SIAM.Google Scholar
Duff, I. S. (1974a), ‘On the number of nonzeros added when Gaussian elimination is performed on sparse random matrices’, Math. Comp. 28, 219–230.Google Scholar
Duff, I. S. (1974b), ‘Pivot selection and row ordering in Givens reductions on sparse matrices’, Computing 13, 239–248.Google Scholar
Duff, I. S. (1977a), ‘On permutations to block triangular form’, IMA J. Appl. Math. 19, 339–342.Google Scholar
Duff, I. S. (1977b), ‘A survey of sparse matrix research’, Proc. IEEE 65, 500–535.Google Scholar
Duff, I. S. (1979), Practical comparisons of codes for the solution of sparse linear systems. In Sparse Matrix Proceedings (Duff, I. S. and Stewart, G. W., eds), SIAM, pp. 107–134.Google Scholar
Duff, I. S. (1981a), ‘Algorithm 575: Permutations for a zero-free diagonal’, ACM Trans. Math. Softw. 7, 387–390.Google Scholar
Duff, I. S. (1981b), ‘ME28: A sparse unsymmetric linear equation solver for complex equations’, ACM Trans. Math. Softw. 7, 505–511.CrossRefGoogle Scholar
Duff, I. S. (1981c), ‘On algorithms for obtaining a maximum transversal’, ACM Trans. Math. Softw. 7, 315–330.Google Scholar
Duff, I. S. (1981d), A sparse future. In Sparse Matrices and their Uses (Duff, I. S., ed.), Academic, pp. 1–29.Google Scholar
Duff, I. S. (1981e), Sparse Matrices and their Uses, Academic.Google Scholar
Duff, I. S. (1984a), ‘Design features of a frontal code for solving sparse unsymmetric linear systems out-of-core’, SIAM J. Sci. Comput. 5, 270–280.Google Scholar
Duff, I. S. (1984b), ‘Direct methods for solving sparse systems of linear equations’, SIAM J. Sci. Comput. 5, 605–619.Google Scholar
Duff, I. S. (1984c), The solution of nearly symmetric sparse linear systems. In Computing Methods in Applied Sciences and Engineering, VI: Proc. 6th International Symposium (Glowinski, R. and Lions, J.-L., eds), North-Holland, pp. 57–74.Google Scholar
Duff, I. S. (1984d), The solution of sparse linear systems on the CRAY-1. In High-Speed Computation (Kowalik, J. S., ed.), Springer, pp. 293–309.Google Scholar
Duff, I. S. (1984e), A survey of sparse matrix software. In Sources and Development of Mathematical Software (Cowell, W. R., ed.), Prentice-Hall, pp. 165–199.Google Scholar
Duff, I. S. (1985), Data structures, algorithms and software for sparse matrices. In Sparsity and its Applications (Evans, D. J., ed.), Cambridge University Press, pp. 1–29.Google Scholar
Duff, I. S. (1986a), ‘Parallel implementation of multifrontal schemes’, Parallel Comput. 3, 193–204.Google Scholar
Duff, I. S. (1986b), The parallel solution of sparse linear equations. In CONPAR 86, Proc. Conference on Algorithms and Hardware for Parallel Processing (Handler, W., Haupt, D., Jeltsch, R., Juling, W. and Lange, O., eds), Vol. 237 of Lecture Notes in Computer Science, Springer, pp. 18–24.Google Scholar
Duff, I. S. (1989a), ‘Direct solvers’, Computer Physics Reports 11, 1–20.Google Scholar
Duff, I. S. (1989b), ‘Multiprocessing a sparse matrix code on the Alliant FX/8’, J. Comput. Appl. Math. 27, 229–239.Google Scholar
Duff, I. S. (1989c), Parallel algorithms for sparse matrix solution. In Parallel Computing: Methods, Algorithms, and Applications (Evans, D. J. and Sutti, C., eds), Adam Hilger Ltd, Bristol, pp. 73–82.Google Scholar
Duff, I. S. (1990), ‘The solution of large-scale least-squares problems on supercomputers’, Ann. Oper. Res. 22, 241–252.Google Scholar
Duff, I. S. (1991), Parallel algorithms for general sparse systems. In Computer Algorithms for Solving Linear Algebraic Equations (Spedicato, E., ed.), Vol. 77 of NATO ASI Series, Springer, pp. 277–297.Google Scholar
Duff, I. S. (1996), ‘A review of frontal methods for solving linear systems’, Computer Physics Comm. 97, 45–52.Google Scholar
Duff, I. S. (2000), ‘The impact of high-performance computing in the solution of linear systems: Trends and problems’, J. Comput. Appl. Math. 123, 515–530.Google Scholar
Duff, I. S. (2004), ‘MA57: A code for the solution of sparse symmetric definite and indefinite systems’, ACM Trans. Math. Softw. 30, 118–144.Google Scholar
Duff, I. S. (2007), ‘Developments in matching and scaling algorithms’, Proc. Applied Math. Mech. 7, 1010801–1010802.CrossRefGoogle Scholar
Duff, I. S. (2009), ‘The design and use of a sparse direct solver for skew symmetric matrices’, J. Comput. Appl. Math. 226, 50–54.Google Scholar
Duff, I. S. and Johnsson, L. S. (1989), Node orderings and concurrency in structurally-symmetric sparse problems. Chapter 12 of Parallel Supercomputing: Methods, Algorithms, and Applications (Carey, G. F., ed.), Wiley, pp. 177–189.Google Scholar
Duff, I. S. and Koster, J. (1999), ‘The design and use of algorithms for permuting large entries to the diagonal of sparse matrices’, SIAM J. Matrix Anal. Appl. 20, 889–901.CrossRefGoogle Scholar
Duff, I. S. and Koster, J. (2001), ‘On algorithms for permuting large entries to the diagonal of a sparse matrix’, SIAM J. Matrix Anal. Appl. 22, 973–996.Google Scholar
Duff, I. S. and Pralet, S. (2005), ‘Strategies for scaling and pivoting for sparse symmetric indefinite problems’, SIAM J. Matrix Anal. Appl. 27, 313–340.Google Scholar
Duff, I. S. and Pralet, S. (2007), ‘Towards stable mixed pivoting strategies for the sequential and parallel solution of sparse symmetric indefinite systems’, SIAM J. Matrix Anal. Appl. 29, 1007–1024.Google Scholar
Duff, I. S. and Reid, J. K. (1974), ‘A comparison of sparsity orderings for obtaining a pivotal sequence in Gaussian elimination’, IMA J. Appl. Math. 14, 281–291.Google Scholar
Duff, I. S. and Reid, J. K. (1976), ‘A comparison of some methods for the solution of sparse overdetermined systems of linear equations’, IMA J. Appl. Math. 17, 267–280.Google Scholar
Duff, I. S. and Reid, J. K. (1978a), ‘Algorithm 529: Permutations to block triangular form’, ACM Trans. Math. Softw. 4, 189–192.Google Scholar
Duff, I. S. and Reid, J. K. (1978b), ‘An implementation of Tarjan’s algorithm for the block triangularization of a matrix’, ACM Trans. Math. Softw. 4, 137–147.Google Scholar
Duff, I. S. and Reid, J. K. (1979a), Performance evaluation of codes for sparse matrix problems. In Performance Evaluation of Numerical Software; Proc. IFIP TC 2.5 Working Conference (Fosdick, L. D., ed.), North-Holland, pp. 121–135.Google Scholar
Duff, I. S. and Reid, J. K. (1979b), ‘Some design features of a sparse matrix code’, ACM Trans. Math. Softw. 5, 18–35.Google Scholar
Duff, I. S. and Reid, J. K. (1982), ‘Experience of sparse matrix codes on the CRAY-1’, Computer Physics Comm. 26, 293–302.Google Scholar
Duff, I. S. and Reid, J. K. (1983a), ‘The multifrontal solution of indefinite sparse symmetric linear equations’, ACM Trans. Math. Softw. 9, 302–325.Google Scholar
Duff, I. S. and Reid, J. K. (1983b), ‘A note on the work involved in no-fill sparse matrix factorization’, IMA J. Numer. Anal. 3, 37–40.Google Scholar
Duff, I. S. and Reid, J. K. (1984), ‘The multifrontal solution of unsymmetric sets of linear equations’, SIAM J. Sci. Comput. 5, 633–641.Google Scholar
Duff, I. S. and Reid, J. K. (1996a), ‘The design of MA48: A code for the direct solution of sparse unsymmetric linear systems of equations’, ACM Trans. Math. Softw. 22, 187–226.Google Scholar
Duff, I. S. and Reid, J. K. (1996b), ‘Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems’, ACM Trans. Math. Softw. 22, 227–257.Google Scholar
Duff, I. S. and Scott, J. A. (1996), ‘The design of a new frontal code for solving sparse, unsymmetric systems’, ACM Trans. Math. Softw. 22, 30–45.Google Scholar
Duff, I. S. and Scott, J. A. (1999), ‘A frontal code for the solution of sparse positive-definite symmetric systems arising from finite-element applications’, ACM Trans. Math. Softw. 25, 404–424.Google Scholar
Duff, I. S. and Scott, J. A. (2004), ‘A parallel direct solver for large sparse highly unsymmetric linear systems’, ACM Trans. Math. Softw. 30, 95–117.Google Scholar
Duff, I. S. and Scott, J. A. (2005), ‘Stabilized bordered block diagonal forms for parallel sparse solvers’, Parallel Comput. 31, 275–289.Google Scholar
Duff, I. S. and Uçar, B. (2010), ‘On the block triangular form of symmetric matrices’, SIAM Review 52, 455–470.Google Scholar
Duff, I. S. and Uçar, B. (2012), Combinatorial problems in solving linear systems. Chapter 2 of Combinatorial Scientific Computing (Schenk, O., ed.), Chapman & Hall/CRC Computational Science, pp. 21–68.Google Scholar
Duff, I. S. and Van der Vorst, H. A. (1999), ‘Developments and trends in the parallel solution of linear systems’, Parallel Comput. 25, 1931–1970.Google Scholar
Duff, I. S. and Wiberg, T. (1988), ‘Implementations of $\text{O}(\sqrt{n}t)$ assignment algorithms’, ACM Trans. Math. Softw. 14, 267–287.Google Scholar
Duff, I. S., Erisman, A. M. and Reid, J. K. (1976), ‘On George’s nested dissection method’, SIAM J. Numer. Anal. 13, 686–695.Google Scholar
Duff, I. S., Erisman, A. M. and Reid, J. K. (1986), Direct Methods for Sparse Matrices, Oxford University Press.Google Scholar
Duff, I. S., Erisman, A. M., Gear, C. W. and Reid, J. K. (1988), ‘Sparsity structure and Gaussian elimination’, ACM SIGNUM Newsletter 23, 2–8.Google Scholar
Duff, I. S., Gould, N. I. M., Lescrenier, M. and Reid, J. K. (1990), The multifrontal method in a parallel environment. In Reliable Numerical Computation (Cox, M. G. and Hammarling, S., eds), Oxford University Press, pp. 93–111.Google Scholar
Duff, I. S., Gould, N. I. M., Reid, J. K., Scott, J. A. and Turner, K. (1991), ‘The factorization of sparse symmetric indefinite matrices’, IMA J. Numer. Anal. 11, 181–204.Google Scholar
Duff, I. S., Grimes, R. G. and Lewis, J. G. (1989a), ‘Sparse matrix test problems’, ACM Trans. Math. Softw. 15, 1–14.Google Scholar
Duff, I. S., Kaya, K. and Uçar, B. (2011), ‘Design, implementation, and analysis of maximum transversal algorithms’, ACM Trans. Math. Softw. 38, 13:1–13:31.Google Scholar
Duff, I. S., Reid, J. K. and Scott, J. A. (1989b), ‘The use of profile reduction algorithms with a frontal code’, Intl J. Numer. Methods Eng. 28, 2555–2568.Google Scholar
Duff, I. S., Reid, J. K., Munksgaard, J. K. and Nielsen, H. B. (1979), ‘Direct solution of sets of linear equations whose matrix is sparse, symmetric and indefinite’, IMA J. Appl. Math. 23, 235–250.Google Scholar
Dulmage, A. L. and Mendelsohn, N. S. (1963), ‘Two algorithms for bipartite graphs’, J. SIAM 11, 183–194.Google Scholar
Edlund, O. (2002), ‘A software package for sparse orthogonal factorization and updating’, ACM Trans. Math. Softw. 28, 448–482.Google Scholar
Eisenstat, S. C. and Liu, J. W. H. (1992), ‘Exploiting structural symmetry in unsymmetric sparse symbolic factorization’, SIAM J. Matrix Anal. Appl. 13, 202–211.Google Scholar
Eisenstat, S. C. and Liu, J. W. H. (1993a), ‘Exploiting structural symmetry in a sparse partial pivoting code’, SIAM J. Sci. Comput. 14, 253–257.Google Scholar
Eisenstat, S. C. and Liu, J. W. H. (1993b), Structural representations of Schur complements in sparse matrices. In Graph Theory and Sparse Matrix Computation (George, A., Gilbert, J. R. and Liu, J. W. H., eds), Vol. 56 of IMA Volumes in Applied Mathematics, Springer, pp. 85–100.Google Scholar
Eisenstat, S. C. and Liu, J. W. H. (2005a), ‘The theory of elimination trees for sparse unsymmetric matrices’, SIAM J. Matrix Anal. Appl. 26, 686–705.Google Scholar
Eisenstat, S. C. and Liu, J. W. H. (2005b), ‘A tree based dataflow model for the unsymmetric multifrontal method’, Electron. Trans. Numer. Anal. 21, 1–19.Google Scholar
Eisenstat, S. C. and Liu, J. W. H. (2008), ‘Algorithmic aspects of elimination trees for sparse unsymmetric matrices’, SIAM J. Matrix Anal. Appl. 29, 1363–1381.Google Scholar
Eisenstat, S. C., Gursky, M. C., Schultz, M. H. and Sherman, A. H. (1977), The Yale sparse matrix package II: The non-symmetric codes. Technical report 114, Department of Computer Science, Yale University.Google Scholar
Eisenstat, S. C., Gursky, M. C., Schultz, M. H. and Sherman, A. H. (1982), ‘Yale sparse matrix package I: The symmetric codes’, Intl J. Numer. Methods Eng. 18, 1145–1151.Google Scholar
Eisenstat, S. C., Schultz, M. H. and Sherman, A. H. (1975), ‘Efficient implementation of sparse symmetric Gaussian elimination’, Adv. Comput Methods Partial Diff. Equations, pp. 33–39.Google Scholar
Eisenstat, S. C., Schultz, M. H. and Sherman, A. H. (1976a), Applications of an element model for Gaussian elimination. In Sparse Matrix Computations (Bunch, J. R. and Rose, D. J., eds), Academic, pp. 85–96.Google Scholar
Eisenstat, S. C., Schultz, M. H. and Sherman, A. H. (1976b), Considerations in the design of software for sparse Gaussian elimination. In Sparse Matrix Computations (Bunch, J. R. and Rose, D. J., eds), Academic, pp. 263–273.Google Scholar
Eisenstat, S. C., Schultz, M. H. and Sherman, A. H. (1979), Software for sparse Gaussian elimination with limited core storage. In Sparse Matrix Proceedings (Duff, I. S. and Stewart, G. W., eds), SIAM, pp. 135–153.Google Scholar
Eisenstat, S. C., Schultz, M. H. and Sherman, A. H. (1981), ‘Algorithms and data structures for sparse symmetric Gaussian elimination’, SIAM J. Sci. Comput. 2, 225–237.Google Scholar
Erisman, A. M., Grimes, R. G., Lewis, J. G. and Poole, W. G. (1985), ‘A structurally stable modification of Hellerman–Rarick’s P4 algorithm for reordering unsymmetric sparse matrices’, SIAM J. Numer. Anal. 22, 369–385.Google Scholar
Erisman, A. M., Grimes, R. G., Lewis, J. G., Poole, W. G. and Simon, H. D. (1987), ‘Evaluation of orderings for unsymmetric sparse matrices’, SIAM J. Sci. Comput. 8, 600–624.Google Scholar
Eswar, K., Huang, C.-H. and Sadayappan, P. (1994), Memory-adaptive parallel sparse Cholesky factorization. In Proc. Scalable High-Performance Computing Conference, 1994, pp. 317–323.Google Scholar
Eswar, K., Huang, C.-H. and Sadayappan, P. (1995), On mapping data and computation for parallel sparse Cholesky factorization. In Proc. 5th Symp. Frontiers of Massively Parallel Computation, pp. 171–178.Google Scholar
Eswar, K., Sadayappan, P. and Visvanathan, V. (1993a), Parallel direct solution of sparse linear systems. In Parallel Computing on Distributed Memory Multiprocessors (Özgüner, F. and Erçal, F., eds), Vol. 103 of NATO ASI Series, Springer, pp. 119–142.Google Scholar
Eswar, K., Sadayappan, P., Huang, C.-H. and Visvanathan, V. (1993b), Supernodal sparse Cholesky factorization on distributed-memory multiprocessors. In Proc. International Conference on Parallel Processing: ICPP93,Vol. 3, pp. 18–22.Google Scholar
D. J. Evans, ed. (1985), Sparsity and its Applications, Cambridge University Press.Google Scholar
Everstine, G. C. (1979), ‘A comparison of three resequencing algorithms for the reduction of matrix profile and wavefront’, Intl J. Numer. Methods Eng. 14, 837–853.Google Scholar
Felippa, C. A. (1975), ‘Solution of linear equations with skyline-stored symmetric matrix’, Comput. Struct. 5, 13–29.Google Scholar
Fenves, S. J. and Law, K. H. (1983), ‘A two-step approach to finite element ordering’, Intl J. Numer. Methods Eng. 19, 891–911.Google Scholar
Fiduccia, C. M. and Mattheyses, R. M. (1982), A linear-time heuristic for improving network partition. In Proc. 19th Design Automation Conference, pp. 175–181.Google Scholar
Fiedler, M. (1973), ‘Algebraic connectivity of graphs’, Czechoslovak Math J. 23, 298–305.Google Scholar
Forrest, J. J. H. and Tomlin, J. A. (1972), ‘Updated triangular factors of the basis to maintain sparsity in the product form simplex method’, Math. Program. 2, 263–278.Google Scholar
Foster, L. V. and Davis, T. A. (2013), ‘Algorithm 933: Reliable calculation of numerical rank, null space bases, pseudoinverse solutions and basic solutions using SuiteSparseQR’, ACM Trans. Math. Softw. 40, 7:1–7:23.Google Scholar
Fu, C., Jiao, X. and Yang, T. (1998), ‘Efficient sparse LU factorization with partial pivoting on distributed memory architectures’, IEEE Trans. Parallel Distrib. Systems 9, 109–125.Google Scholar
Gallivan, K. A., Hansen, P. C., Ostromsky, T. and Zlatev, Z. (1995), ‘A locally optimized reordering algorithm and its application to a parallel sparse linear system solver’, Computing 54, 39–67.Google Scholar
Gallivan, K. A., Marsolf, B. A. and Wijshoff, H. A. G. (1996), ‘Solving large nonsymmetric sparse linear systems using MCSPARSE’, Parallel Comput. 22, 1291–1333.Google Scholar
Gao, F. and Parlett, B. N. (1990), ‘A note on communication analysis of parallel sparse Cholesky factorization on a hypercube’, Parallel Comput. 16, 59–60.Google Scholar
Gay, D. M. (1991), ‘Massive memory buys little speed for complete, in-core sparse Cholesky factorizations on some scalar computers’, Linear Algebra Appl. 152, 291–314.Google Scholar
Geist, G. A. and Ng, E. G. (1989), ‘Task scheduling for parallel sparse Cholesky factorization’, Intl J. Parallel Program. 18, 291–314.Google Scholar
Geng, P., Oden, J. T. and van de Geijn, R. A. (1997), ‘A parallel multifrontal algorithm and its implementation’, Comput. Methods Appl. Mech. Eng. 149, 289–301.Google Scholar
Gentleman, W. M. (1975), Row elimination for solving sparse linear systems and least squares problems. In Numerical Analysis (Watson, G. A., ed.), Vol. 506 of Lecture Notes in Mathematics, Springer, pp. 122–133.Google Scholar
George, A. (1972), Block elimination on finite element systems of equations. In Sparse Matrices and their Applications (Rose, D. J. and Willoughby, R. A., eds), Plenum, pp. 101–114.Google Scholar
George, A. (1973), ‘Nested dissection of a regular finite element mesh’, SIAM J. Numer. Anal. 10, 345–363.Google Scholar
George, A. (1974), ‘On block elimination for sparse linear systems’, SIAM J. Numer. Anal. 11, 585–603.Google Scholar
George, A. (1977a), ‘Numerical experiments using dissection methods to solve $n$-by-$n$ grid problems’, SIAM J. Numer. Anal. 14, 161–179.Google Scholar
George, A. (1977b), Solution of linear systems of equations: Direct methods for finite-element problems. In Sparse Matrix Techniques (Barker, V. A., ed.), Vol. 572 of Lecture Notes in Mathematics, Springer, pp. 52–101.Google Scholar
George, A. (1980), ‘An automatic one-way dissection algorithm for irregular finite-element problems’, SIAM J. Numer. Anal. 17, 740–751.Google Scholar
George, A. (1981), Direct solution of sparse positive definite systems: Some basic ideas and open problems. In Sparse Matrices and their Uses (Duff, I. S., ed.), Academic, pp. 283–306.Google Scholar
George, A. and Heath, M. T. (1980), ‘Solution of sparse linear least squares problems using Givens rotations’, Linear Algebra Appl. 34, 69–83.Google Scholar
George, A. and Liu, J. W. H. (1975), ‘A note on fill for sparse matrices’, SIAM J. Numer. Anal. 12, 452–454.Google Scholar
George, A. and Liu, J. W. H. (1978a), ‘Algorithms for matrix partitioning and the numerical solution of finite element systems’, SIAM J. Numer. Anal. 15, 297–327.Google Scholar
George, A. and Liu, J. W. H. (1978b), ‘An automatic nested dissection algorithm for irregular finite element problems’, SIAM J. Numer. Anal. 15, 1053–1069.Google Scholar
George, A. and Liu, J. W. H. (1979a), ‘The design of a user interface for a sparse matrix package’, ACM Trans. Math. Softw. 5, 139–162.Google Scholar
George, A. and Liu, J. W. H. (1979b), ‘An implementation of a pseudo-peripheral node finder’, ACM Trans. Math. Softw. 5, 284–295.Google Scholar
George, A. and Liu, J. W. H. (1980a), ‘A fast implementation of the minimum degree algorithm using quotient graphs’, ACM Trans. Math. Softw. 6, 337–358.Google Scholar
George, A. and Liu, J. W. H. (1980b), ‘A minimal storage implementation of the minimum degree algorithm’, SIAM J. Numer. Anal. 17, 282–299.Google Scholar
George, A. and Liu, J. W. H. (1980c), ‘An optimal algorithm for symbolic factorization of symmetric matrices’, SIAM J. Comput. 9, 583–593.Google Scholar
George, A. and Liu, J. W. H. (1981), Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall.Google Scholar
George, A. and Liu, J. W. H. (1987), ‘Householder reflections versus Givens rotations in sparse orthogonal decomposition’, Linear Algebra Appl. 88, 223–238.Google Scholar
George, A. and Liu, J. W. H. (1989), ‘The evolution of the minimum degree ordering algorithm’, SIAM Review 31, 1–19.Google Scholar
George, A. and Liu, J. W. H. (1999), ‘An object-oriented approach to the design of a user interface for a sparse matrix package’, SIAM J. Matrix Anal. Appl. 20, 953–969.Google Scholar
George, A. and Mcintyre, D. R. (1978), ‘On the application of the minimum degree algorithm to finite element systems’, SIAM J. Numer. Anal. 15, 90–112.Google Scholar
George, A. and Ng, E. G. (1983), ‘On row and column orderings for sparse least square problems’, SIAM J. Numer. Anal. 20, 326–344.Google Scholar
George, A. and Ng, E. G. (1984a), ‘A new release of SPARSPAK: The Waterloo sparse matrix package’, ACM SIGNUM Newsletter 19, 9–13.Google Scholar
George, A. and Ng, E. G. (1984b), SPARSPAK: Waterloo sparse matrix package, user’s guide for SPARSPAK-B. Technical report CS-84-37, Department of Computer Science, University of Waterloo, Ontario. https://cs.uwaterloo.ca/research/tr/1984/CS-84-37.pdfGoogle Scholar
George, A. and Ng, E. G. (1985a), ‘A brief description of SPARSPAK: Waterloo sparse linear equations package’, ACM SIGNUM Newsletter 16, 17–19.Google Scholar
George, A. and Ng, E. G. (1985b), ‘An implementation of Gaussian elimination with partial pivoting for sparse systems’, SIAM J. Sci. Comput. 6, 390–409.Google Scholar
George, A. and Ng, E. G. (1986), ‘Orthogonal reduction of sparse matrices to upper triangular form using Householder transformations’, SIAM J. Sci. Comput. 7, 460–472.Google Scholar
George, A. and Ng, E. G. (1987), ‘Symbolic factorization for sparse Gaussian elimination with partial pivoting’, SIAM J. Sci. Comput. 8, 877–898.Google Scholar
George, A. and Ng, E. G. (1988), ‘On the complexity of sparse QR and LU factorization of finite-element matrices’, SIAM J. Sci. Comput. 9, 849–861.Google Scholar
George, A. and Ng, E. G. (1990), ‘Parallel sparse Gaussian elimination with partial pivoting’, Ann. Oper. Res. 22, 219–240.Google Scholar
George, A. and Pothen, A. (1997), ‘An analysis of spectral envelope-reduction via quadratic assignment problems’, SIAM J. Matrix Anal. Appl. 18, 706–732.Google Scholar
George, A. and Rashwan, H. (1980), ‘On symbolic factorization of partitioned sparse symmetric matrices’, Linear Algebra Appl. 34, 145–157.Google Scholar
George, A. and Rashwan, H. (1985), ‘Auxiliary storage methods for solving finite element systems’, SIAM J. Sci. Comput. 6, 882–910.Google Scholar
George, A., Heath, M. T. and Ng, E. G. (1983), ‘A comparison of some methods for solving sparse linear least-squares problems’, SIAM J. Sci. Comput. 4, 177–187.Google Scholar
George, A., Heath, M. T. and Ng, E. G. (1984a), ‘Solution of sparse underdetermined systems of linear equations’, SIAM J. Sci. Comput. 5, 988–997.Google Scholar
George, A., Heath, M. T. and Plemmons, R. J. (1981), ‘Solution of large-scale sparse least squares problems using auxiliary storage’, SIAM J. Sci. Comput. 2, 416–429.Google Scholar
George, A., Heath, M. T., Liu, J. W. H. and Ng, E. G. (1986a), ‘Solution of sparse positive definite systems on a shared-memory multiprocessor’, Intl J. Parallel Program. 15, 309–325.Google Scholar
George, A., Heath, M. T., Liu, J. W. H. and Ng, E. G. (1988a), ‘Sparse Cholesky factorization on a local-memory multiprocessor’, SIAM J. Sci. Comput. 9, 327–340.Google Scholar
George, A., Heath, M. T., Liu, J. W. H. and Ng, E. G. (1989a), ‘Solution of sparse positive definite systems on a hypercube’, J. Comput. Appl. Math. 27, 129–156.Google Scholar
George, A., Heath, M. T., Ng, E. G. and Liu, J. W. H. (1987), ‘Symbolic Cholesky factorization on a local-memory multiprocessor’, Parallel Comput. 5, 85–95.Google Scholar
George, A., Liu, J. W. H. and Ng, E. G. (1984b), ‘Row ordering schemes for sparse Givens transformations I: Bipartite graph model’, Linear Algebra Appl. 61, 55–81.Google Scholar
George, A., Liu, J. W. H. and Ng, E. G. (1986b), ‘Row ordering schemes for sparse Givens transformations II: Implicit graph model’, Linear Algebra Appl. 75, 203–223.Google Scholar
George, A., Liu, J. W. H. and Ng, E. G. (1986c), ‘Row ordering schemes for sparse Givens transformations III: Analysis for a model problem’, Linear Algebra Appl. 75, 225–240.Google Scholar
George, A., Liu, J. W. H. and Ng, E. G. (1988b), ‘A data structure for sparse QR and LU factorizations’, SIAM J. Sci. Comput. 9, 100–121.Google Scholar
George, A., Liu, J. W. H. and Ng, E. G. (1989b), ‘Communication results for parallel sparse Cholesky factorization on a hypercube’, Parallel Comput. 10, 287–298.Google Scholar
George, A., Poole, W. G. and Voigt, R. G. (1978), ‘Incomplete nested dissection for solving $n$-by-$n$ grid problems’, SIAM J. Numer. Anal. 15, 662–673.Google Scholar
George, J. A. (1971), Computer implementation of the finite element method. Technical report STAN-CS-71-208, Department of Computer Science, Stanford University.Google Scholar
George, T., Saxena, V., Gupta, A., Singh, A. and Choudhury, A. R. (2011), Multifrontal factorization of sparse SPD matrices on GPUs. In Proc. 2011 IEEE International Parallel Distributed Processing Symposium: IPDPS, pp. 372–383.Google Scholar
Geschiere, J. P. and Wijshoff, H. A. G. (1995), ‘Exploiting large grain parallelism in a sparse direct linear system solver’, Parallel Comput. 21, 1339–1364.Google Scholar
Gibbs, N. E. (1976), ‘Algorithm 509: A hybrid profile reduction algorithm’, ACM Trans. Math. Softw. 2, 378–387.Google Scholar
Gibbs, N. E., Poole, W. G. and Stockmeyer, P. K. (1976a), ‘An algorithm for reducing the bandwidth and profile of a sparse matrix’, SIAM J. Numer. Anal. 13, 236–250.Google Scholar
Gibbs, N. E., Poole, W. G. and Stockmeyer, P. K. (1976b), ‘A comparison of several bandwidth and reduction algorithms’, ACM Trans. Math. Softw. 2, 322–330.Google Scholar
Gilbert, J. R. (1980), ‘A note on the NP-completeness of vertex elimination on directed graphs’, SIAM J. Alg. Discrete Methods 1, 292–294.Google Scholar
Gilbert, J. R. (1994), ‘Predicting structure in sparse matrix computations’, SIAM J. Matrix Anal. Appl. 15, 62–79.Google Scholar
Gilbert, J. R. and Grigori, L. (2003), ‘A note on the column elimination tree’, SIAM J. Matrix Anal. Appl. 25, 143–151.Google Scholar
Gilbert, J. R. and Hafsteinsson, H. (1990), ‘Parallel symbolic factorization of sparse linear systems’, Parallel Comput. 14, 151–162.Google Scholar
Gilbert, J. R. and Liu, J. W. H. (1993), ‘Elimination structures for unsymmetric sparse LU factors’, SIAM J. Matrix Anal. Appl. 14, 334–354.Google Scholar
Gilbert, J. R. and Ng, E. G. (1993), Predicting structure in nonsymmetric sparse matrix factorizations. In Graph Theory and Sparse Matrix Computation (George, A., Gilbert, J. R. and Liu, J. W. H., eds), Vol. 56 of IMA Volumes in Applied Mathematics, Springer, pp. 107–139.Google Scholar
Gilbert, J. R. and Peierls, T. (1988), ‘Sparse partial pivoting in time proportional to arithmetic operations’, SIAM J. Sci. Comput. 9, 862–874.Google Scholar
Gilbert, J. R. and Schreiber, R. (1992), ‘Highly parallel sparse Cholesky factorization’, SIAM J. Sci. Comput. 13, 1151–1172.Google Scholar
Gilbert, J. R. and Tarjan, R. E. (1987), ‘The analysis of a nested dissection algorithm’, Numer. Math. 50, 377–404.Google Scholar
Gilbert, J. R. and Zmijewski, E. (1987), ‘A parallel graph partitioning algorithm for a message-passing multiprocessor’, Intl J. Parallel Program. 16, 427–449.Google Scholar
Gilbert, J. R., Li, X. S., Ng, E. G. and Peyton, B. W. (2001), ‘Computing row and column counts for sparse QR and LU factorization’, BIT Numer. Math. 41, 693–710.Google Scholar
Gilbert, J. R., Miller, G. L. and Teng, S. H. (1998), ‘Geometric mesh partitioning: Implementation and experiments’, SIAM J. Sci. Comput. 19, 2091–2110.Google Scholar
Gilbert, J. R., Moler, C. and Schreiber, R. (1992), ‘Sparse matrices in MATLAB: Design and implementation’, SIAM J. Matrix Anal. Appl. 13, 333–356.Google Scholar
Gilbert, J. R., Ng, E. G. and Peyton, B. W. (1994), ‘An efficient algorithm to compute row and column counts for sparse Cholesky factorization’, SIAM J. Matrix Anal. Appl. 15, 1075–1091.Google Scholar
Gilbert, J. R., Ng, E. G. and Peyton, B. W. (1997), ‘Separators and structure prediction in sparse orthogonal factorization’, Linear Algebra Appl. 262, 83–97.Google Scholar
Gillespie, M. I. and Olesky, D. D. (1995), ‘Ordering Givens rotations for sparse QR factorization’, SIAM J. Matrix Anal. Appl. 16, 1024–1041.Google Scholar
Golub, G. H. and Van Loan, C. F. (2012), Matrix Computations, fourth edition, Johns Hopkins Studies in the Mathematical Sciences, The Johns Hopkins University Press.Google Scholar
González, P., Cabaleiro, J. C. and Pena, T. F. (2000), ‘On parallel solvers for sparse triangular systems’, J. Systems Architecture 46, 675–685.Google Scholar
Goto, K. and van de Geijn, R. (2008), ‘High performance implementation of the level-3 BLAS’, ACM Trans. Math. Softw. 35, 14:1–14:14.Google Scholar
Gould, N. I. M. and Scott, J. A. (2004), ‘A numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations’, ACM Trans. Math. Softw. 30, 300–325.Google Scholar
Gould, N. I. M., Scott, J. A. and Hu, Y. (2007), ‘A numerical evaluation of sparse solvers for symmetric systems’, ACM Trans. Math. Softw. 33, 10:1–10:32.Google Scholar
Grigori, L. and Li, X. S. (2007), ‘Towards an accurate performance modelling of parallel sparse factorization’, Appl. Algebra Eng. Comm. Comput. 18, 241–261.Google Scholar
Grigori, L., Boman, E., Donfack, S. and Davis, T. A. (2010), ‘Hypergraph-based unsymmetric nested dissection ordering for sparse LU factorization’, SIAM J. Sci. Comput. 32, 3426–3446.Google Scholar
Grigori, L., Cosnard, M. and Ng, E. G. (2007a), ‘On the row merge tree for sparse LU factorization with partial pivoting’, BIT Numer. Math. 47, 45–76.Google Scholar
Grigori, L., Demmel, J. W. and Li, X. S. (2007b), ‘Parallel symbolic factorization for sparse LU with static pivoting’, SIAM J. Sci. Comput. 29, 1289–1314.Google Scholar
Grigori, L., Gilbert, J. R. and Cosnard, M. (2009), ‘Symbolic and exact structure prediction for sparse Gaussian elimination with partial pivoting’, SIAM J. Matrix Anal. Appl. 30, 1520–1545.Google Scholar
Grimes, R. G., Pierce, D. J. and Simon, H. D. (1990), ‘A new algorithm for finding a pseudoperipheral node in a graph’, SIAM J. Matrix Anal. Appl. 11, 323–334.Google Scholar
Guermouche, A. and L’Excellent, J.-Y. (2006), ‘Constructing memory-minimizing schedules for multifrontal methods’, ACM Trans. Math. Softw. 32, 17–32.Google Scholar
Guermouche, A., L’Excellent, J.-Y. and Utard, G. (2003), ‘Impact of reordering on the memory of a multifrontal solver’, Parallel Comput. 29, 1191–1218.Google Scholar
Gunnels, J. A., Gustavson, F. G., Henry, G. M. and van de Geijn, R. A. (2001), ‘FLAME: Formal linear algebra methods environment’, ACM Trans. Math. Softw. 27, 422–455.Google Scholar
Gupta, A. (1996a), Fast and effective algorithms for graph partitioning and sparse matrix ordering. Technical report RC 20496 (90799), IBM Research Division, Yorktown Heights, NY.Google Scholar
Gupta, A. (1996b), WGPP: Watson graph partitioning. Technical report RC 20453 (90427), IBM Research Division, Yorktown Heights, NY.Google Scholar
Gupta, A. (2002a), ‘Improved symbolic and numerical factorization algorithms for unsymmetric sparse matrices’, SIAM J. Matrix Anal. Appl. 24, 529–552.Google Scholar
Gupta, A. (2002b), ‘Recent advances in direct methods for solving unsymmetric sparse systems of linear equations’, ACM Trans. Math. Softw. 28, 301–324.Google Scholar
Gupta, A. (2007), ‘A shared- and distributed-memory parallel general sparse direct solver’, Appl. Algebra Eng. Comm. Comput. 18, 263–277.Google Scholar
Gupta, A., Karypis, G. and Kumar, V. (1997), ‘Highly scalable parallel algorithms for sparse matrix factorization’, IEEE Trans. Parallel Distrib. Systems 8, 502–520.Google Scholar
Gustavson, F. G. (1972), Some basic techniques for solving sparse systems of linear equations. In Sparse Matrices and their Applications (Rose, D. J. and Willoughby, R. A., eds), Plenum, pp. 41–52.Google Scholar
Gustavson, F. G. (1976), Finding the block lower triangular form of a sparse matrix. In Sparse Matrix Computations (Bunch, J. R. and Rose, D. J., eds), Academic, pp. 275–290.Google Scholar
Gustavson, F. G. (1978), ‘Two fast algorithms for sparse matrices: Multiplication and permuted transposition’, ACM Trans. Math. Softw. 4, 250–269.Google Scholar
Gustavson, F. G., Liniger, W. M. and Willoughby, R. A. (1970), ‘Symbolic generation of an optimal Crout algorithm for sparse systems of linear equations’, J. Assoc. Comput. Mach. 17, 87–109.Google Scholar
Hachtel, G., Brayton, R. and Gustavson, F. (1971), ‘The sparse tableau approach to network analysis and design’, IEEE Trans. Circuit Theory 18, 101–113.Google Scholar
Hadfield, S. M. and Davis, T. A. (1994), Potential and achievable parallelism in the unsymmetric-pattern multifrontal LU factorization method for sparse matrices. In Proc. 5th SIAM Conference on Applied Linear Algebra, SIAM, pp. 387–391.Google Scholar
Hadfield, S. M. and Davis, T. A. (1995), ‘The use of graph theory in a parallel multifrontal method for sequences of unsymmetric pattern sparse matrices’, Congress. Numer. 108, 43–52.Google Scholar
Hager, W. W. (2002), ‘Minimizing the profile of a symmetric matrix’, SIAM J. Sci. Comput. 23, 1799–1816.Google Scholar
Hare, D. R., Johnson, C. R., Olesky, D. D. and van den Driessche, P. (1993), ‘Sparsity analysis of the QR factorization’, SIAM J. Matrix Anal. Appl. 14, 665–669.Google Scholar
He, K., Tan, S. X.-D., Wang, H. and Shi, G. (2015), ‘GPU-accelerated parallel sparse LU factorization method for fast circuit analysis’, IEEE Trans. VLSI Sys. 24, 1140–1150.Google Scholar
Heath, M. T. (1982), ‘Some extensions of an algorithm for sparse linear least squares problems’, SIAM J. Sci. Comput. 3, 223–237.Google Scholar
Heath, M. T. (1984), ‘Numerical methods for large sparse linear least squares problems’, SIAM J. Sci. Comput. 5, 497–513.Google Scholar
Heath, M. T. and Raghavan, P. (1995), ‘A Cartesian parallel nested dissection algorithm’, SIAM J. Matrix Anal. Appl. 16, 235–253.Google Scholar
Heath, M. T. and Raghavan, P. (1997), ‘Performance of a fully parallel sparse solver’, Intl J. Supercomp. Appl. High Perf. Comput. 11, 49–64.Google Scholar
Heath, M. T. and Sorensen, D. C. (1986), ‘A pipelined Givens method for computing the QR factorization of a sparse matrix’, Linear Algebra Appl. 77, 189–203.Google Scholar
Heath, M. T., Ng, E. G. and Peyton, B. W. (1991), ‘Parallel algorithms for sparse linear systems’, SIAM Review 33, 420–460.Google Scholar
Heggernes, P. and Peyton, B. W. (2008), ‘Fast computation of minimal fill inside a given elimination ordering’, SIAM J. Matrix Anal. Appl. 30, 1424–1444.Google Scholar
Hellerman, E. and Rarick, D. C. (1971), ‘Reinversion with the preassigned pivot procedure’, Math. Program. 1, 195–216.Google Scholar
Hellerman, E. and Rarick, D. C. (1972), The partitioned preassigned pivot procedure (P4). In Sparse Matrices and their Applications (Rose, D. J. and Willoughby, R. A., eds), Plenum, pp. 67–76.Google Scholar
Hendrickson, B. and Leland, R. (1995a), The Chaco users guide: Version 2.0. Technical report SAND95-2344, Sandia National Laboratories.Google Scholar
Hendrickson, B. and Leland, R. (1995b), A multilevel algorithm for partitioning graphs. In Supercomputing ’95: Proc. 1995 ACM/IEEE Conference on Supercomputing, p. 28.Google Scholar
Hendrickson, B. and Rothberg, E. (1998), ‘Improving the runtime and quality of nested dissection ordering’, SIAM J. Sci. Comput. 20, 468–489.Google Scholar
Hénon, P., Ramet, P. and Roman, J. (2002), ‘PaStiX: A high-performance parallel direct solver for sparse symmetric definite systems’, Parallel Comput. 28, 301–321.Google Scholar
Ho, C.-W. and Lee, R. C. T. (1990), ‘A parallel algorithm for solving sparse triangular systems’, IEEE Trans. Comput. 39, 848–852.Google Scholar
Hogg, J. D. and Scott, J. A. (2013a), ‘An efficient analyse phase for element problems’, Numer. Linear Algebra Appl. 20, 397–412.Google Scholar
Hogg, J. D. and Scott, J. A. (2013b), ‘New parallel sparse direct solvers for multicore architectures’, Algorithms 6, 702–725.Google Scholar
Hogg, J. D. and Scott, J. A. (2013c), ‘Optimal weighted matchings for rank-deficient sparse matrices’, SIAM J. Matrix Anal. Appl. 34, 1431–1447.Google Scholar
Hogg, J. D. and Scott, J. A. (2013d), ‘Pivoting strategies for tough sparse indefinite systems’, ACM Trans. Math. Softw. 40, 4:1–4:19.Google Scholar
Hogg, J. D., Ovtchinnikov, E. and Scott, J. A. (2016), ‘A sparse symmetric indefinite direct solver for GPU architectures’, ACM Trans. Math. Softw. 42, 1:1–1:25.Google Scholar
Hogg, J. D., Reid, J. K. and Scott, J. A. (2010), ‘Design of a multicore sparse Cholesky factorization using DAGs’, SIAM J. Sci. Comput. 32, 3627–3649.Google Scholar
Hoit, M. and Wilson, E. L. (1983), ‘An equation numbering algorithm based on a minimum front criteria’, Comput. Struct. 16, 225–239.Google Scholar
Hood, P. (1976), ‘Frontal solution program for unsymmetric matrices’, Intl J. Numer. Methods Eng. 10, 379–400.Google Scholar
Hopcroft, J. E. and Karp, R. M. (1973), ‘An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs’, SIAM J. Comput. 2, 225–231.Google Scholar
Huang, J. W. and Wing, O. (1979), ‘Optimal parallel triangulation of a sparse matrix’, IEEE Trans. Circuits and Systems CAS‐26, 726–732.Google Scholar
Hulbert, L. and Zmijewski, E. (1991), ‘Limiting communication in parallel sparse Cholesky factorization’, SIAM J. Sci. Comput. 12, 1184–1197.Google Scholar
Igual, F. D., Chan, E., Quintana-Ortí, E. S., Quintana-Ortí, G., van de Geijn, R. A. and Van Zee, F. G. (2012), ‘The FLAME approach: From dense linear algebra algorithms to high-performance multi-accelerator implementations’, J. Parallel Distrib. Comput. 72, 1134–1143.Google Scholar
Irons, B. M. (1970), ‘A frontal solution program for finite element analysis’, Intl J. Numer. Methods Eng. 2, 5–32.Google Scholar
Irony, D., Shklarski, G. and Toledo, S. (2004), ‘Parallel and fully recursive multifrontal sparse Cholesky’, Future Generation Comp. Sys. 20, 425–440.Google Scholar
Jennings, A. (1966), ‘A compact storage scheme for the solution of symmetric linear simultaneous equations’, Comput.J. 9, 281–285.Google Scholar
Jess, J. A. G. and Kees, H. G. M. (1982), ‘A data structure for parallel LU decomposition’, IEEE Trans. Comput. C‐31, 231–239.Google Scholar
Joshi, M., Karypis, G., Kumar, V., Gupta, A. and Gustavson, F. (1999), PSPASES: An efficient and scalable parallel sparse direct solver. In Proc. 9th SIAM Conference on Parallel Processing for Scientific Computing (Yang, T., ed.), Vol. 515 of Kluwer International Series in Engineering and Science, Kluwer. www-users.cs.umn.edu/∼mjoshi/pspases/Google Scholar
Karypis, G., Aggarwal, R., Kumar, V. and Shekhar, S. (1999), ‘Multilevel hypergraph partitioning: Applications in VLSI domain’, IEEE Trans. Very Large Scale Integration (VLSI) Systems 7, 69–79.Google Scholar
Karypis, G. and Kumar, V. (1998a), ‘A fast and high quality multilevel scheme for partitioning irregular graphs’, SIAM J. Sci. Comput. 20, 359–392.Google Scholar
Karypis, G. and Kumar, V. (1998b), hMETIS 1.5: A hypergraph partitioning package. Technical report, Department of Computer Science and Engineering University of Minnesota.Google Scholar
Karypis, G. and Kumar, V. (1998c), ‘A parallel algorithm for multilevel graph partitioning and sparse matrix ordering’, J. Parallel Distrib. Comput. 48, 71–95.Google Scholar
Karypis, G. and Kumar, V. (2000), ‘Multilevel k-way hypergraph partitioning’, VLSI Design 11, 285–300.Google Scholar
Kayaaslan, E., Pinar, A., Çatalyürek, U. V. and Aykanat, C. (2012), ‘Partitioning hypergraphs in scientific computing applications through vertex separators on graphs’, SIAM J. Sci. Comput. 34, A970–A992.Google Scholar
Kernighan, B. W. and Lin, S. (1970), ‘An efficient heuristic procedure for partitioning graphs’, Bell System Tech. J. 49, 291–307.Google Scholar
Kim, K. and Eijkhout, V. (2014), ‘A parallel sparse direct solver via hierarchical DAG scheduling’, ACM Trans. Math. Softw. 41, 3:1–3:27.Google Scholar
King, I. P. (1970), ‘An automatic reordering scheme for simultaneous equations derived from network systems’, Intl J. Numer. Methods Eng. 2, 523–533.Google Scholar
Knuth, D. E. (1972), ‘George Forsythe and the development of computer science’, Comm. Assoc. Comput. Mach. 15, 721–726.Google Scholar
Koster, J. and Bisseling, R. H. (1994), An improved algorithm for parallel sparse LU decomposition on a distributed-memory multiprocessor. In Proc. 5th SIAM Conference on Applied Linear Algebra, SIAM, pp. 397–401.Google Scholar
Kratzer, S. G. (1992), ‘Sparse QR factorization on a massively parallel computer’, J. Supercomputing 6, 237–255.Google Scholar
Kratzer, S. G. and Cleary, A. J. (1993), Sparse matrix factorization on SIMD parallel computers. In Graph Theory and Sparse Matrix Computation (George, A., Gilbert, J. R. and Liu, J. W. H., eds), Vol. 56 of IMA Volumes in Applied Mathematics, Springer, pp. 211–228.Google Scholar
Krawezik, G. and Poole, G. (2009), Accelerating the ANSYS direct sparse solver with GPUs. In Proc. Symposium on Application Accelerators in High Performance Computing: SAAHPC, NCSA, Urbana-Champaign, IL.Google Scholar
Kruskal, C. P., Rudolph, L. and Snir, M. (1989), Techniques for parallel manipulation of sparse matrices. In Theoret. Comput. Sci.,Vol. 64, pp. 135–157.Google Scholar
Kumar, B., Eswar, K., Sadayappan, P. and Huang, C.-H. (1994), A reordering and mapping algorithm for parallel sparse Cholesky factorization. In Proc. Scalable High-Performance Computing Conference, 1994, pp. 803–810.Google Scholar
Kumar, P. S., Kumar, M. K. and Basu, A. (1992), ‘A parallel algorithm for elimination tree computation and symbolic factorization’, Parallel Comput. 18, 849–856.Google Scholar
Kumar, P. S., Kumar, M. K. and Basu, A. (1993), ‘Parallel algorithms for sparse triangular system solution’, Parallel Comput. 19, 187–196.Google Scholar
Kumfert, G. K. and Pothen, A. (1997), ‘Two improved algorithms for reducing the envelope and wavefront’, BIT Numer. Math. 37, 559–590.Google Scholar
Kundert, K. S. (1986), Sparse matrix techniques and their applications to circuit simulation. In Circuit Analysis, Simulation and Design (Ruehli, A. E., ed.), North-Holland.Google Scholar
Lacoste, X., Ramet, P., Faverge, M., Ichitaro, Y. and Dongarra, J. (2012), Sparse direct solvers with accelerators over DAG runtimes. Technical report RR-7972, INRIA, Bordeaux.Google Scholar
Law, K. H. (1985), ‘Sparse matrix factor modification in structural reanalysis’, Intl J. Numer. Methods Eng. 21, 37–63.Google Scholar
Law, K. H. (1989), ‘On updating the structure of sparse matrix factors’, Intl J. Numer. Methods Eng. 28, 2339–2360.Google Scholar
Law, K. H. and Fenves, S. J. (1986), ‘A node-addition model for symbolic factorization’, ACM Trans. Math. Softw. 12, 37–50.Google Scholar
Law, K. H. and Mackay, D. R. (1993), ‘A parallel row-oriented sparse solution method for finite element structural analysis’, Intl J. Numer. Methods Eng. 36, 2895–2919.Google Scholar
Lee, H., Kim, J., Hong, S. J. and Lee, S. (2003), ‘Task scheduling using a block dependency DAG for block-oriented sparse Cholesky factorization’, Parallel Comput. 29, 135–159.Google Scholar
Leuze, M. (1989), ‘Independent set orderings for parallel matrix factorization by Gaussian elimination’, Parallel Comput. 10, 177–191.Google Scholar
Levy, R. (1971), ‘Resequencing of the structural stiffness matrix to improve computational efficiency’, Quarterly Technical Review 1, 61–70.Google Scholar
Lewis, J. G. (1982a), ‘Algorithm 582: The Gibbs–Poole–Stockmeyer and Gibbs–King algorithms for reordering sparse matrices’, ACM Trans. Math. Softw. 8, 190–194.Google Scholar
Lewis, J. G. (1982b), ‘Implementation of the Gibbs–Poole–Stockmeyer and Gibbs–King algorithms’, ACM Trans. Math. Softw. 8, 180–189.Google Scholar
Lewis, J. G. and Simon, H. D. (1988), ‘The impact of hardware gather/scatter on sparse Gaussian elimination’, SIAM J. Sci. Comput. 9, 304–311.Google Scholar
Lewis, J. G., Peyton, B. W. and Pothen, A. (1989), ‘A fast algorithm for reordering sparse matrices for parallel factorization’, SIAM J. Sci. Comput. 10, 1146–1173.Google Scholar
L’Excellent, J.-Y. and Sid-Lakhdar, W. M. (2014), ‘Introduction of shared-memory parallelism in a distributed-memory multifrontal solver’, Parallel Comput. 40, 34–46.Google Scholar
Li, X. S. (2005), ‘An overview of SuperLU: Algorithms, implementation, and user interface’, ACM Trans. Math. Softw. 31, 302–325.Google Scholar
Li, X. S. (2008), ‘Evaluation of SuperLU on multicore architectures’, J. Physics: Conference Series 125, 012079.Google Scholar
Li, X. S. (2013), Direct solvers for sparse matrices. Technical report, Lawrence Berkeley National Laboratory, Berkeley. http://crd-legacy.lbl.gov/∼xiaoye/SuperLU/SparseDirectSurvey.pdfGoogle Scholar
Li, X. S. and Demmel, J. W. (2003), ‘SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems’, ACM Trans. Math. Softw. 29, 110–140.Google Scholar
Lin, T. D. and Mah, R. S. H. (1977), ‘Hierarchical partition: A new optimal pivoting algorithm’, Math. Program. 12, 260–278.Google Scholar
Lin, W.-Y. and Chen, C.-L. (1999), ‘Minimum communication cost reordering for parallel sparse Cholesky factorization’, Parallel Comput. 25, 943–967.Google Scholar
Lin, W.-Y. and Chen, C.-L. (2000), ‘On evaluating elimination tree based parallel sparse Cholesky factorizations’, Intl J. Comput. Math. 74, 361–377.Google Scholar
Lin, W.-Y. and Chen, C.-L. (2005), ‘On optimal reorderings of sparse matrices for parallel Cholesky factorizations’, SIAM J. Matrix Anal. Appl. 27, 24–45.Google Scholar
Lipton, R. J. and Tarjan, R. E. (1979), ‘A separator theorem for planar graphs’, SIAM J. Appl. Math. 36, 177–189.Google Scholar
Lipton, R. J., Rose, D. J. and Tarjan, R. E. (1979), ‘Generalized nested dissection’, SIAM J. Numer. Anal. 16, 346–358.Google Scholar
Liu, J. W. H. (1985), ‘Modification of the minimum-degree algorithm by multiple elimination’, ACM Trans. Math. Softw. 11, 141–153.Google Scholar
Liu, J. W. H. (1986a), ‘A compact row storage scheme for Cholesky factors using elimination trees’, ACM Trans. Math. Softw. 12, 127–148.Google Scholar
Liu, J. W. H. (1986b), ‘Computational models and task scheduling for parallel sparse Cholesky factorization’, Parallel Comput. 3, 327–342.Google Scholar
Liu, J. W. H. (1986c), ‘On general row merging schemes for sparse Givens transformations’, SIAM J. Sci. Comput. 7, 1190–1211.Google Scholar
Liu, J. W. H. (1986d), ‘On the storage requirement in the out-of-core multifrontal method for sparse factorization’, ACM Trans. Math. Softw. 12, 249–264.Google Scholar
Liu, J. W. H. (1987a), ‘An adaptive general sparse out-of-core Cholesky factorization scheme’, SIAM J. Sci. Comput. 8, 585–599.Google Scholar
Liu, J. W. H. (1987b), ‘An application of generalized tree pebbling to sparse matrix factorization’, SIAM J. Alg. Discrete Methods 8, 375–395.Google Scholar
Liu, J. W. H. (1987c), ‘A note on sparse factorization in a paging environment’, SIAM J. Sci. Comput. 8, 1085–1088.Google Scholar
Liu, J. W. H. (1987d), ‘On threshold pivoting in the multifrontal method for sparse indefinite systems’, ACM Trans. Math. Softw. 13, 250–261.Google Scholar
Liu, J. W. H. (1987e), ‘A partial pivoting strategy for sparse symmetric matrix decomposition’, ACM Trans. Math. Softw. 13, 173–182.Google Scholar
Liu, J. W. H. (1988a), ‘Equivalent sparse matrix reordering by elimination tree rotations’, SIAM J. Sci. Comput. 9, 424–444.Google Scholar
Liu, J. W. H. (1988b), ‘A tree model for sparse symmetric indefinite matrix factorization’, SIAM J. Matrix Anal. Appl. 9, 26–39.Google Scholar
Liu, J. W. H. (1989a), ‘A graph partitioning algorithm by node separators’, ACM Trans. Math. Softw. 15, 198–219.Google Scholar
Liu, J. W. H. (1989b), ‘The minimum degree ordering with constraints’, SIAM J. Sci. Comput. 10, 1136–1145.Google Scholar
Liu, J. W. H. (1989c), ‘The multifrontal method and paging in sparse Cholesky factorization’, ACM Trans. Math. Softw. 15, 310–325.Google Scholar
Liu, J. W. H. (1989d), ‘Reordering sparse matrices for parallel elimination’, Parallel Comput. 11, 73–91.Google Scholar
Liu, J. W. H. (1990), ‘The role of elimination trees in sparse factorization’, SIAM J. Matrix Anal. Appl. 11, 134–172.Google Scholar
Liu, J. W. H. (1991), ‘A generalized envelope method for sparse factorization by rows’, ACM Trans. Math. Softw. 17, 112–129.Google Scholar
Liu, J. W. H. (1992), ‘The multifrontal method for sparse matrix solution: Theory and practice’, SIAM Review 34, 82–109.Google Scholar
Liu, J. W. H. and Mirzaian, A. (1989), ‘A linear reordering algorithm for parallel pivoting of chordal graphs’, SIAM J. Discrete Math. 2, 100–107.Google Scholar
Liu, J. W. H. and Sherman, A. H. (1976), ‘Comparative analysis of the Cuthill–McKee and the reverse Cuthill–McKee ordering algorithms for sparse matrices’, SIAM J. Numer. Anal. 13, 198–213.Google Scholar
Liu, J. W. H., Ng, E. G. and Peyton, B. W. (1993), ‘On finding supernodes for sparse matrix computations’, SIAM J. Matrix Anal. Appl. 14, 242–252.Google Scholar
Lu, S. M. and Barlow, J. L. (1996), ‘Multifrontal computation with the orthogonal factors of sparse matrices’, SIAM J. Matrix Anal. Appl. 17, 658–679.Google Scholar
Lucas, R. F., Blank, T. and Tiemann, J. J. (1987), ‘A parallel solution method for large sparse systems of equations’, IEEE Trans. Computer-Aided Design Integ. Circ. Sys. 6, 981–991.Google Scholar
Lucas, R. F., Wagenbreth, G., Davis, D. and Grimes, R. G. (2010), Multifrontal computations on GPUs and their multi-core hosts. In VECPAR’10: Proc. 9th International Meeting for High Performance Computing for Computational Science. http://vecpar.fe.up.pt/2010/papers/5.phpGoogle Scholar
Luce, R. and Ng, E. G. (2014), ‘On the minimum FLOPs problem in the sparse Cholesky factorization’, SIAM J. Matrix Anal. Appl. 35, 1–21.Google Scholar
Manne, F. and Haffsteinsson, H. (1995), ‘Efficient sparse Cholesky factorization on a massively parallel SIMD computer’, SIAM J. Sci. Comput. 16, 934–950.Google Scholar
Markowitz, H. M. (1957), ‘The elimination form of the inverse and its application to linear programming’, Management Sci. 3, 255–269.Google Scholar
Marro, L. (1986), ‘A linear time implementation of profile reduction algorithms for sparse matrices’, SIAM J. Sci. Comput. 7, 1212–1231.Google Scholar
Matstoms, P. (1994), ‘Sparse QR factorization in MATLAB’, ACM Trans. Math. Softw. 20, 136–159.Google Scholar
Matstoms, P. (1995), ‘Parallel sparse QR factorization on shared memory architectures’, Parallel Comput. 21, 473–486.Google Scholar
Mayer, J. (2009), ‘Parallel algorithms for solving linear systems with sparse triangular matrices’, Computing 86, 291–312.Google Scholar
Mcnamee, J. M. (1971), ‘ACM Algorithm 408: A sparse matrix package I’, Comm. Assoc. Comput. Mach. 14, 265–273.Google Scholar
Mcnamee, J. M. (1983a), ‘Algorithm 601: A sparse matrix package II: Special cases’, ACM Trans. Math. Softw. 9, 344–345.Google Scholar
Mcnamee, J. M. (1983b), ‘A sparse matrix package II: Special cases’, ACM Trans. Math. Softw. 9, 340–343.Google Scholar
Melhem, R. G. (1988), ‘A modified frontal technique suitable for parallel systems’, SIAM J. Sci. Comput. 9, 289–303.Google Scholar
Meshar, O., Irony, D. and Toledo, S. (2006), ‘An out-of-core sparse symmetric-indefinite factorization method’, ACM Trans. Math. Softw. 32, 445–471.Google Scholar
Miller, G. L., Teng, S. H., Thurston, W. and Vavasis, S. A. (1993), Automatic mesh partitioning. In Graph Theory and Sparse Matrix Computation (George, A., Gilbert, J. R. and Liu, J. W. H., eds), Vol. 56 of IMA Volumes in Applied Mathematics, Springer, pp. 57–84.Google Scholar
Nakhla, M., Singhal, K. and Vlach, J. (1974), ‘An optimal pivoting order for the solution of sparse systems of equations’, IEEE Trans. Circuits and Systems CAS‐21, 222–225.Google Scholar
Ng, E. G. (1991), ‘A scheme for handling rank-deficiency in the solution of sparse linear least squares problems’, SIAM J. Sci. Comput. 12, 1173–1183.Google Scholar
Ng, E. G. (1993), ‘Supernodal symbolic Cholesky factorization on a local-memory multiprocessor’, Parallel Comput. 19, 153–162.Google Scholar
Ng, E. G. (2013), Sparse matrix methods. Chapter 53 of Handbook of Linear Algebra, second edition, Chapman & Hall/CRC, pp. 931–951.Google Scholar
Ng, E. G. and Peyton, B. W. (1992), ‘A tight and explicit representation of Q in sparse QR factorization’, IMA Preprint Series.Google Scholar
Ng, E. G. and Peyton, B. W. (1993a), ‘Block sparse Cholesky algorithms on advanced uniprocessor computers’, SIAM J. Sci. Comput. 14, 1034–1056.Google Scholar
Ng, E. G. and Peyton, B. W. (1993b), ‘A supernodal Cholesky factorization algorithm for shared-memory multiprocessors’, SIAM J. Sci. Comput. 14, 761–769.Google Scholar
Ng, E. G. and Peyton, B. W. (1996), ‘Some results on structure prediction in sparse QR factorization’, SIAM J. Matrix Anal. Appl. 17, 443–459.Google Scholar
Ng, E. G. and Raghavan, P. (1999), ‘Performance of greedy ordering heuristics for sparse Cholesky factorization’, SIAM J. Matrix Anal. Appl. 20, 902–914.Google Scholar
Norin, R. S. and Pottle, C. (1971), ‘Effective ordering of sparse matrices arising from nonlinear electrical networks’, IEEE Trans. Circuit Theory CT‐18, 139–145.Google Scholar
Oliveira, S. (2001), ‘Exact prediction of QR fill-in by row-merge trees’, SIAM J. Sci. Comput. 22, 1962–1973.Google Scholar
Olschowka, M. and Neumaier, A. (1996), ‘A new pivoting strategy for Gaussian elimination’, Linear Algebra Appl. 240, 131–151.Google Scholar
Ong, J. H. (1987), ‘An algorithm for frontwidth reduction’, J. Sci. Comput. 2, 159–173.Google Scholar
Osterby, O. and Zlatev, Z. (1983), Direct Methods for Sparse Matrices, Vol. 157 of Lecture Notes in Computer Science, Springer. Review by Eisenstat at: http://dx.doi.org/10.1137/1028128Google Scholar
Ostromsky, T., Hansen, P. C. and Zlatev, Z. (1998), ‘A coarse-grained parallel QR-factorization algorithm for sparse least squares problems’, Parallel Comput. 24, 937–964.Google Scholar
Ostrouchov, G. (1993), ‘Symbolic Givens reduction and row-ordering in large sparse least squares problems’, SIAM J. Matrix Anal. Appl. 8, 248–264.Google Scholar
Padmini, M. V., Madan, B. B. and Jain, B. N. (1998), ‘Reordering for parallelism’, Intl J. Comput. Math. 67, 373–390.Google Scholar
Paige, C. C. and Saunders, M. A. (1982), ‘LSQR: An algorithm for sparse linear equations and sparse least squares’, ACM Trans. Math. Softw. 8, 43–71.Google Scholar
Papadimitriou, C. H. (1976), ‘The NP-completeness of the bandwidth minimization problem’, Computing 16, 263–270.Google Scholar
Parter, S. V. (1961), ‘The use of linear graphs in Gauss elimination’, SIAM Review 3, 119–130.Google Scholar
Pellegrini, F. (2012), Scotch and PT-Scotch graph partitioning software. Chapter 14 of Combinatorial Scientific Computing (Schenk, O., ed.), Chapman & Hall/ CRC Computational Science, pp. 373–406.Google Scholar
Pellegrini, F., Roman, J. and Amestoy, P. R. (2000), ‘Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering’, Concurrency: Pract. Exp. 12, 68–84.Google Scholar
Peters, F. J. (1984), ‘Parallel pivoting algorithms for sparse symmetric matrices’, Parallel Comput. 1, 99–110.Google Scholar
Peters, F. J. (1985), Parallelism and sparse linear equations. In Sparsity and its Applications (Evans, D. J., ed.), Cambridge University Press, pp. 285–301.Google Scholar
Peters, G. and Wilkinson, J. H. (1970), ‘The least squares problem and pseudo-inverses’, Comput. J. 13, 309–316.Google Scholar
Peyton, B. W. (2001), ‘Minimal orderings revisited’, SIAM J. Matrix Anal. Appl. 23, 271–294.Google Scholar
Peyton, B. W., Pothen, A. and Yuan, X. (1993), ‘Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution’, Linear Algebra Appl. 192, 329–354.Google Scholar
Peyton, B. W., Pothen, A. and Yuan, X. (1995), ‘A clique tree algorithm for partitioning a chordal graph into transitive subgraphs’, Linear Algebra Appl. 223/224, 553–588.Google Scholar
Pierce, D. J. and Lewis, J. G. (1997), ‘Sparse multifrontal rank revealing QR factorization’, SIAM J. Matrix Anal. Appl. 18, 159–180.Google Scholar
Pierce, D. J., Hung, Y., Liu, C.-C., Tsai, Y.-H., Wang, W. and Yu, D. (2009), Sparse multifrontal performance gains via NVIDIA GPU. In Workshop on GPU Supercomputing, National Taiwan University, Taipei. http://cqse.ntu.edu.tw/cqse/gpu2009.htmlGoogle Scholar
Pina, H. L. G. (1981), ‘An algorithm for frontwidth reduction’, Intl J. Numer. Methods Eng. 17, 1539–1546.Google Scholar
Pissanetsky, S. (1984), Sparse Matrix Technology, Academic.Google Scholar
Pothen, A. (1993), ‘Predicting the structure of sparse orthogonal factors’, Linear Algebra Appl. 194, 183–204.Google Scholar
Pothen, A. (1996), Graph partitioning algorithms with applications to scientific computing. In Parallel Numerical Algorithms (Keyes, D. E., Sameh, A. H. and Venkatakrishnan, V., eds), Kluwer Academic, pp. 323–368.Google Scholar
Pothen, A. and Alvarado, F. L. (1992), ‘A fast reordering algorithm for parallel sparse triangular solution’, SIAM J. Sci. Comput. 13, 645–653.Google Scholar
Pothen, A. and Fan, C. (1990), ‘Computing the block triangular form of a sparse matrix’, ACM Trans. Math. Softw. 16, 303–324.Google Scholar
Pothen, A. and Sun, C. (1990), Compact clique tree data structures in sparse matrix factorizations. Chapter 12 of Large Scale Numerical Optimization (Coleman, T. F. and Li, Y., eds), SIAM.Google Scholar
Pothen, A. and Sun, C. (1993), ‘A mapping algorithm for parallel sparse Cholesky factorization’, SIAM J. Sci. Comput. 14, 1253–1257.Google Scholar
Pothen, A. and Toledo, S. (2004), Elimination structures in scientific computing. Chapter 59 of Handbook on Data Structures and Applications (Mehta, D. and Sahni, S., eds), Chapman & Hall/CRC.Google Scholar
Pothen, A., Simon, H. D. and Liou, K. (1990), ‘Partitioning sparse matrices with eigenvectors of graphs’, SIAM J. Matrix Anal. Appl. 11, 430–452.Google Scholar
Pouransari, H., Coulier, P. and Darve, E. (2015), Fast hierarchical solvers for sparse matrices. Technical report, Department of Mechanical Engineering, Stanford University, and Department of Civil Engineering, KU Leuven. arXiv:1510.07363Google Scholar
Raghavan, P. (1995), ‘Distributed sparse Gaussian elimination and orthogonal factorization’, SIAM J. Sci. Comput. 16, 1462–1477.Google Scholar
Raghavan, P. (1997), ‘Parallel ordering using edge contraction’, Parallel Comput. 23, 1045–1067.Google Scholar
Raghavan, P. (1998), ‘Efficient parallel sparse triangular solution using selective inversion’, Parallel Processing Letters 8, 29–40.Google Scholar
Raghavan, P. (2002), DSCPACK: Domain-separator codes for the parallel solution of sparse linear systems. Technical report CSE-02-004, Penn State University, State College, PA. www.cse.psu.edu/∼pxr3/software.htmlGoogle Scholar
Rauber, T., Rünger, G. and Scholtes, C. (1999), ‘Scalability of sparse Cholesky factorization’, Intl J. High Speed Computing 10, 19–52.Google Scholar
Razzaque, A. (1980), ‘Automatic reduction of frontwidth for finite element analysis’, Intl J. Numer. Methods Eng. 25, 1315–1324.Google Scholar
Reid, J. K. (1971), Large Sparse Sets of Linear Equations, Academic.Google Scholar
Reid, J. K. (1974), Direct methods for sparse matrices. In Software for Numerical Mathematics (Evans, D. J., ed.), Academic, pp. 29–48.Google Scholar
Reid, J. K. (1977a), Solution of linear systems of equations: Direct methods (general). In Sparse Matrix Techniques (Barker, V. A., ed.), Vol. 572 of Lecture Notes in Mathematics, Springer, pp. 102–129.Google Scholar
Reid, J. K. (1977b), Sparse matrices. In The State of the Art in Numerical Analysis (Jacobs, D. A. H., ed.), Academic, pp. 85–146.Google Scholar
Reid, J. K. (1981), Frontal methods for solving finite-element systems of linear equations. In Sparse Matrices and their Uses (Duff, I. S., ed.), Academic, pp. 265–281.Google Scholar
Reid, J. K. (1982), ‘A sparsity-exploiting variant of the Bartels–Golub decomposition for linear programming bases’, Math. Program. 24, 55–69.Google Scholar
Reid, J. K. and Scott, J. A. (1999), ‘Ordering symmetric sparse matrices for small profile and wavefront’, Intl J. Numer. Methods Eng. 45, 1737–1755.Google Scholar
Reid, J. K. and Scott, J. A. (2001), ‘Reversing the row order for the row-by-row frontal method’, Numer. Linear Algebra Appl. 8, 1–6.Google Scholar
Reid, J. K. and Scott, J. A. (2002), ‘Implementing Hager’s exchange methods for matrix profile reduction’, ACM Trans. Math. Softw. 28, 377–391.Google Scholar
Reid, J. K. and Scott, J. A. (2009a), ‘An efficient out-of-core multifrontal solver for large-scale unsymmetric element problems’, Intl J. Numer. Methods Eng. 77, 901–921.Google Scholar
Reid, J. K. and Scott, J. A. (2009b), ‘An out-of-core sparse Cholesky solver’, ACM Trans. Math. Softw. 36, 9:1–9:33.Google Scholar
Reiszig, G. (2007), ‘Local fill reduction techniques for sparse symmetric linear systems’, Electr. Eng. 89, 639–652.Google Scholar
Rennich, S. C., Stosic, D. and Davis, T. A. (2014), Accelerating sparse Cholesky factorization on GPUs. In Proc. 4th Workshop on Irregular Applications: Architectures and Algorithms, IEEE, pp. 9–16.Google Scholar
Robey, T. H. and Sulsky, D. L. (1994), ‘Row orderings for a sparse QR decomposition’, SIAM J. Matrix Anal. Appl. 15, 1208–1225.Google Scholar
Rose, D. J. (1972), A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In Graph Theory and Computing (Read, R. C., ed.), Academic, pp. 183–217.Google Scholar
Rose, D. J. and Bunch, J. R. (1972), The role of partitioning in the numerical solution of sparse systems. In Sparse Matrices and their Applications (Rose, D. J. and Willoughby, R. A., eds), Plenum, pp. 177–187.Google Scholar
Rose, D. J. and Tarjan, R. E. (1978), ‘Algorithmic aspects of vertex elimination on directed graphs’, SIAM J. Appl. Math. 34, 176–197.Google Scholar
D. J. Rose and R. A. Willoughby, eds (1972), Sparse Matrices and their Applications, Plenum.Google Scholar
Rose, D. J., Tarjan, R. E. and Lueker, G. S. (1976), ‘Algorithmic aspects of vertex elimination on graphs’, SIAM J. Comput. 5, 266–283.Google Scholar
Rose, D. J., Whitten, G. G., Sherman, A. H. and Tarjan, R. E. (1980), ‘Algorithms and software for in-core factorization of sparse symmetric positive definite matrices’, Comput. Struct. 11, 597–608.Google Scholar
Rothberg, E. (1995), ‘Alternatives for solving sparse triangular systems on distributed-memory computers’, Parallel Comput. 21, 1121–1136.Google Scholar
Rothberg, E. (1996), ‘Performance of panel and block approaches to sparse Cholesky factorization on the iPSC/860 and Paragon multicomputers’, SIAM J. Sci. Comput. 17, 699–713.Google Scholar
Rothberg, E. and Eisenstat, S. C. (1998), ‘Node selection strategies for bottom-up sparse matrix orderings’, SIAM J. Matrix Anal. Appl. 19, 682–695.Google Scholar
Rothberg, E. and Gupta, A. (1991), ‘Efficient sparse matrix factorization on high-performance workstations: Exploiting the memory hierarchy’, ACM Trans. Math. Softw. 17, 313–334.Google Scholar
Rothberg, E. and Gupta, A. (1993), ‘An evaluation of left-looking, right-looking, and multifrontal approaches to sparse Cholesky factorization on hierarchical-memory machines’, Intl J. High Speed Computing 5, 537–593.Google Scholar
Rothberg, E. and Gupta, A. (1994), ‘An efficient block-oriented approach to parallel sparse Cholesky factorization’, SIAM J. Sci. Comput. 15, 1413–1439.Google Scholar
Rothberg, E. and Schreiber, R. (1994), Improved load distribution in parallel sparse Cholesky factorization. In Proc. Supercomputing ’94, IEEE, pp. 783–792.Google Scholar
Rothberg, E. and Schreiber, R. (1999), ‘Efficient methods for out-of-core sparse Cholesky factorization’, SIAM J. Sci. Comput. 21, 129–144.Google Scholar
Rotkin, V. and Toledo, S. (2004), ‘The design and implementation of a new out-of-core sparse Cholesky factorization method’, ACM Trans. Math. Softw. 30, 19–46.Google Scholar
Rouet, F.-H., Li, X. S., Ghysels, P. and Napov, A. (2015), A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization. Technical report, Lawrence Berkeley National Laboratory, Berkeley. arXiv:1503.05464Google Scholar
Rozin, E. and Toledo, S. (2005), ‘Locality of reference in sparse Cholesky methods’, Electron. Trans. Numer. Anal. 21, 81–106.Google Scholar
Sadayappan, P. and Visvanathan, V. (1988), ‘Circuit simulation on shared-memory multiprocessors’, IEEE Trans. Comput. 37, 1634–1642.Google Scholar
Sadayappan, P. and Visvanathan, V. (1989), ‘Efficient sparse matrix factorization for circuit simulation on vector supercomputers’, IEEE Trans. Computer-Aided Design Integ. Circ. Sys. 8, 1276–1285.Google Scholar
Sala, M., Stanley, K. S. and Heroux, M. A. (2008), ‘On the design of interfaces to sparse direct solvers’, ACM Trans. Math. Softw. 34, 9:1–9:22.Google Scholar
Saltz, J. H. (1990), ‘Aggregation methods for solving sparse triangular systems on multiprocessors’, SIAM J. Sci. Comput. 11, 123–144.Google Scholar
Sao, P., Liu, X., Vuduc, R. and Li, X. S. (2015), A sparse direct solver for distributed memory Xeon Phi-accelerated systems. In Proc. 29th IEEE International Parallel and Distributed Processing Symposium: IPDPS.Google Scholar
Sao, P., Vuduc, R. and Li, X. S. (2014), A distributed CPU–GPU sparse direct solver. In Vol. 8632 of Lecture Notes in Computer Science (Silva, F., Dutra, I. and Santos Costa, V., eds), Springer, pp. 487–498.Google Scholar
Sato, N. and Tinney, W. F. (1963), ‘Techniques for exploiting the sparsity of the network admittance matrix’, IEEE Trans. Power Apparatus and Systems 82(69), 944–949.Google Scholar
Schenk, O. and Gärtner, K. (2002), ‘Two-level dynamic scheduling in PARDISO: Improved scalability on shared memory multiprocessing systems’, Parallel Comput. 28, 187–197.Google Scholar
Schenk, O. and Gärtner, K. (2004), ‘Solving unsymmetric sparse systems of linear equations with PARDISO’, Future Generation Comp. Sys. 20, 475–487.Google Scholar
Schenk, O. and Gärtner, K. (2006), ‘On fast factorization pivoting methods for sparse symmetric indefinite systems’, Electron. Trans. Numer. Anal. 23, 158–179.Google Scholar
Schenk, O., Gärtner, K. and Fichtner, W. (2000), ‘Efficient sparse LU factorization with left-right looking strategy on shared memory multiprocessors’, BIT Numer. Math. 40, 158–176.Google Scholar
Schenk, O., Gärtner, K., Fichtner, W. and Stricker, A. (2001), ‘PARDISO: A high-performance serial and parallel sparse linear solver in semiconductor device simulation’, Future Generation Comp. Sys. 18, 69–78.Google Scholar
Schreiber, R. (1982), ‘A new implementation of sparse Gaussian elimination’, ACM Trans. Math. Softw. 8, 256–276.Google Scholar
Schreiber, R. (1993), Scalability of sparse direct solvers. In Vol. 56 of IMA Volumes in Applied Mathematics (George, A., Gilbert, J. R. and Liu, J. W. H., eds), Springer, pp. 191–209.Google Scholar
Schulze, J. (2001), ‘Towards a tighter coupling of bottom-up and top-down sparse matrix ordering methods’, BIT Numer. Math. 41, 800–841.Google Scholar
Scott, J. A. (1999a), ‘A new row ordering strategy for frontal solvers’, Numer. Linear Algebra Appl. 6, 189–211.Google Scholar
Scott, J. A. (1999b), ‘On ordering elements for a frontal solver’, Comm. Numer. Methods Eng. 15, 309–324.Google Scholar
Scott, J. A. (2001a), ‘The design of a portable parallel frontal solver for chemical process engineering problems’, Comput. Chem. Eng. 25, 1699–1709.Google Scholar
Scott, J. A. (2001b), ‘A parallel frontal solver for finite element applications’, Intl J. Numer. Methods Eng. 50, 1131–1144.Google Scholar
Scott, J. A. (2003), ‘Parallel frontal solvers for large sparse linear systems’, ACM Trans. Math. Softw. 29, 395–417.Google Scholar
Scott, J. A. (2006), ‘A frontal solver for the 21st century’, Comm. Numer. Methods Eng. 22, 1015–1029.Google Scholar
Scott, J. A. (2010), ‘Scaling and pivoting in an out-of-core sparse direct solver’, ACM Trans. Math. Softw. 37, 19:1–19:23.Google Scholar
Scott, J. A. and Hu, Y. (2007), ‘Experiences of sparse direct symmetric solvers’, ACM Trans. Math. Softw. 33, 18:1–18:28.Google Scholar
Shen, K., Yang, T. and Jiao, X. (2000), ‘S+: Efficient 2D sparse LU factorization on parallel machines’, SIAM J. Matrix Anal. Appl. 22, 282–305.Google Scholar
Sherman, A. H. (1978a), ‘Algorithm 533: NSPIV, a Fortran subroutine for sparse Gaussian elimination with partial pivoting’, ACM Trans. Math. Softw. 4, 391–398.Google Scholar
Sherman, A. H. (1978b), ‘Algorithms for sparse Gaussian elimination with partial pivoting’, ACM Trans. Math. Softw. 4, 330–338.Google Scholar
Silvester, P. P., Auda, H. A. and Stone, G. D. (1984), ‘A memory-economic frontwidth reduction algorithm’, Intl J. Numer. Methods Eng. 20, 733–743.Google Scholar
Sloan, S. W. (1986), ‘An algorithm for profile and wavefront reduction of sparse matrices’, Intl J. Numer. Methods Eng. 23, 239–251.Google Scholar
Slota, G., Rajamanickam, S. and Madduri, K. (2014), BFS and coloring-based parallel algorithms for strongly connected components and related problems. In Proc. 2014 28th IEEE International Parallel and Distributed Processing Symposium, pp. 550–559.Google Scholar
Slota, G., Rajamanickam, S. and Madduri, K. (2015), High-performance graph analytics on manycore processors. In Proc. 2015 IEEE International Parallel and Distributed Processing Symposium: IPDPS, pp. 17–27.Google Scholar
Smart, D. and White, J. (1988), Reducing the parallel solution time of sparse circuit matrices using reordered Gaussian elimination and relaxation. In Proc. IEEE International Symposium Circuits and Systems.Google Scholar
Snay, R. A. (1969), Reducing the profile of sparse symmetric matrices. Technical report NOS NGS-4, National Oceanic and Atmospheric Administration, Washington, DC.Google Scholar
Speelpenning, B. (1978), The generalized element method. Technical report UIUC-DCS-R-78-946, Department of Computer Science, University of Illinois, Urbana, IL.Google Scholar
Srinivas, M. (1983), ‘Optimal parallel scheduling of Gaussian elimination DAG’s’, IEEE Trans. Comput. C‐32, 1109–1117.Google Scholar
Suhl, L. M. and Suhl, U. H. (1993), ‘A fast LU update for linear programming’, Ann. Oper. Res. 43, 33–47.Google Scholar
Suhl, U. H. and Suhl, L. M. (1990), ‘Computing sparse LU factorizations for large-scale linear programming bases’, ORSA J. Comput. 2, 325–335.Google Scholar
Sun, C. (1996), ‘Parallel sparse orthogonal factorization on distributed-memory multiprocessors’, SIAM J. Sci. Comput. 17, 666–685.Google Scholar
Sun, C. (1997), ‘Parallel solution of sparse linear least squares problems on distributed-memory multiprocessors’, Parallel Comput. 23, 2075–2093.Google Scholar
Tarjan, R. E. (1972), ‘Depth first search and linear graph algorithms’, SIAM J. Comput. 1, 146–160.Google Scholar
Tarjan, R. E. (1975), ‘Efficiency of a good but not linear set union algorithm’, J. Assoc. Comput. Mach. 22, 215–225.Google Scholar
Tarjan, R. E. (1976), Graph theory and Gaussian elimination. In Sparse Matrix Computations (Bunch, J. R. and Rose, D. J., eds), Academic, pp. 3–22.Google Scholar
Tewarson, R. P. (1966), ‘On the product form of inverses of sparse matrices’, SIAM Review 8, 336–342.Google Scholar
Tewarson, R. P. (1967a), ‘The product form of inverses of sparse matrices and graph theory’, SIAM Review 9, 91–99.Google Scholar
Tewarson, R. P. (1967b), ‘Row–column permutation of sparse matrices’, Comput. J. 10, 300–305.Google Scholar
Tewarson, R. P. (1967c), ‘Solution of a system of simultaneous linear equations with a sparse coefficient matrix by elimination methods’, BIT Numer. Math. 7, 226–239.Google Scholar
Tewarson, R. P. (1968), ‘On the orthonormalization of sparse vectors’, Computing 3, 268–279.Google Scholar
Tewarson, R. P. (1970), ‘Computations with sparse matrices’, SIAM Review 12, 527–544.Google Scholar
Tewarson, R. P. (1972), ‘On the Gaussian elimination method for inverting sparse matrices’, Computing 9, 1–7.Google Scholar
R. P. Tewarson, ed. (1973), Sparse Matrices, Vol. 99 of Mathematics in Science and Engineering, Academic.Google Scholar
Thompson, E. and Shimazaki, Y. (1980), ‘A frontal procedure using skyline storage’, Intl J. Numer. Methods Eng. 15, 889–910.Google Scholar
Tinney, W. F. and Walker, J. W. (1967), ‘Direct solutions of sparse network equations by optimally ordered triangular factorization’, Proc. IEEE 55, 1801–1809.Google Scholar
Tomlin, J. A. (1972), Modifying triangular factors of the basis in the simplex method. In Sparse Matrices and their Applications (Rose, D. J. and Willoughby, R. A., eds), Plenum, pp. 77–85.Google Scholar
Totoni, E., Heath, M. T. and Kale, L. V. (2014), ‘Structure-adaptive parallel solution of sparse triangular linear systems’, Parallel Comput. 40, 454–470.Google Scholar
Van der Stappen, A. F., Bisseling, R. H. and van de Vorst, J. G. G. (1993), ‘Parallel sparse LU decomposition on a mesh network of transputers’, SIAM J. Matrix Anal. Appl. 14, 853–879.Google Scholar
Vastenhouw, B. and Bisseling, R. H. (2005), ‘A two-dimensional data distribution method for parallel sparse matrix–vector multiplication’, SIAM review 47, 67–95.Google Scholar
Wang, S., Li, X. S., Rouet, F.-H., Xia, J. and De Hoop, M. V. (2016), ‘A parallel geometric multifrontal solver using hierarchically semiseparable structure’, ACM Trans. Math. Softw., to appear.Google Scholar
Webb, J. P. and Froncioni, A. (1986), ‘A time-memory trade-off frontwidth reduction algorithm for finite element analysis’, Intl J. Numer. Methods Eng. 23, 1905–1914.Google Scholar
J. H. Wilkinson and C. Reinsch, eds (1971), Handbook for Automatic Computation, Volume II: Linear Algebra, Springer.Google Scholar
Wing, O. and Huang, J. W. (1980), ‘A computation model of parallel solution of linear equations’, IEEE Trans. Comput. C‐29, 632–638.Google Scholar
Xia, J. (2013a), ‘Efficient structured multifrontal factorization for general large sparse matrices’, SIAM J. Sci. Comput. 35, A832–A860.Google Scholar
Xia, J. (2013b), ‘Randomized sparse direct solvers’, SIAM J. Matrix Anal. Appl. 34, 197–227.Google Scholar
Xia, J., Chandrasekaran, S., Gu, M. and Li, X. S. (2009), ‘Superfast multifrontal method for structured linear systems of equations’, SIAM J. Matrix Anal. Appl. 31, 1382–1411.Google Scholar
Xia, J., Chandrasekaran, S., Gu, M. and Li, X. S. (2010), ‘Fast algorithms for hierarchically semiseparable matrices’, Numer. Linear Algebra Appl. 17, 953–976.Google Scholar
Yannakakis, M. (1981), ‘Computing the minimum fill-in is NP-complete’, SIAM J. Alg. Discrete Methods 2, 77–79.Google Scholar
Yeralan, S. N., Davis, T. A. and Ranka, S. (2015), Sparse QR factorization on the GPU. Technical report, Texas A&M University. http://faculty.cse.tamu.edu/publications.htmlGoogle Scholar
Yu, C. D., Wang, W. and Pierce, D. (2011), ‘A CPU–GPU hybrid approach for the unsymmetric multifrontal method’, Parallel Comput. 37, 759–770.Google Scholar
Zhang, G. and Elman, H. C. (1992), ‘Parallel sparse Cholesky factorization on a shared memory multiprocessor’, Parallel Comput. 18, 1009–1022.Google Scholar
Zlatev, Z. (1980), ‘On some pivotal strategies in Gaussian elimination by sparse technique’, SIAM J. Numer. Anal. 17, 18–30.Google Scholar
Zlatev, Z. (1982), ‘Comparison of two pivotal strategies in sparse plane rotations’, Comput. Math. Appl. 8, 119–135.Google Scholar
Zlatev, Z. (1985), Sparse matrix techniques for general matrices with real elements: Pivotal strategies, decompositions and applications in ODE software. In Sparsity and its Applications (Evans, D. J., ed.), Cambridge University Press, pp. 185–228.Google Scholar
Zlatev, Z. (1987), ‘A survey of the advances in the exploitation of the sparsity in the solution of large problems’, J. Comput. Appl. Math. 20, 83–105.Google Scholar
Zlatev, Z. (1991), Computational Methods for General Sparse Matrices, Kluwer Academic.Google Scholar
Zlatev, Z. and Thomsen, P. G. (1981), Sparse matrices: Efficient decompositions and applications. In Sparse Matrices and their Uses (Duff, I. S., ed.), Academic, pp. 367–375.Google Scholar
Zlatev, Z., Wasniewski, J. and Schaumburg, K. (1981), Y12M: Solution of Large and Sparse Systems of Linear Algebraic Equations, Vol. 121 of Lecture Notes in Computer Science, Springer.Google Scholar
Zmijewski, E. and Gilbert, J. R. (1988), ‘A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor’, Parallel Comput. 7, 199–210.Google Scholar