COLAMD swMATH ID: 145 Software Authors: Davis, Timothy A.; Gilbert, John R.; Larimore, Stefan I.; Ng, Esmond G. Description: Two codes are discussed, COLAMD and SYMAMD, that compute approximate minimum degree orderings for sparse matrices in two contexts: (1) sparse partial pivoting, which requires a sparsity preserving column pre-ordering prior to numerical factorization, and (2) sparse Cholesky factorization, which requires a symmetric permutation of both the rows and columns of the matrix being factorized. These orderings are computed by COLAMD and SYMAMD, respectively. The ordering from COLAMD is also suitable for sparse QR factorization, and the factorization of matrices of the form \(A^TA\) and \(AA^T\), such as those that arise in least-squares problems and interior point methods for linear programming problems. The two routines are available both in MATLAB and \(C\)-callable forms. They appear as built-in routines in MATLAB Version 6.0. Homepage: http://dl.acm.org/citation.cfm?id=1024080 Dependencies: Matlab Related Software: Matlab; SparseMatrix; UMFPACK; symamd; CHOLMOD; LAPACK; AMD; BLAS; SuiteSparseQR; LDL; symrcm; CSparse; CPLEX; HSL; KLU; Ipopt; SuiteSparse; CUDA; ANSYS; Algorithm 980 Referenced in: 33 Publications Standard Articles 2 Publications describing the Software, including 2 Publications in zbMATH Year A column approximate minimum degree ordering algorithm. Zbl 1073.65039Davis, Timothy A.; Gilbert, John R.; Larimore, Stefan I.; Ng, Esmond G. 2004 Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm. Zbl 1070.65535Davis, Timothy A.; Gilbert, John R.; Larimore, Stefan I.; Ng, Esmond G. 2004 all top 5 Referenced by 65 Authors 10 Davis, Timothy Alden 4 Dayar, Tugrul 2 Buchholz, Peter 2 Gilbert, John R. 2 Hager, William W. 2 Larimore, Stefan I. 2 Ng, Esmond G. 2 Toledo, Sivan 1 Ambikasaran, Sivaram 1 Avron, Haim 1 Bao, Yujuan 1 Beuchler, Sven 1 Bollhöfer, Matthias 1 Bomhof, Christiaan Willem 1 Bozkurt, İlker Nadi 1 Cayrols, Sebastien 1 Cheng, Xiaoliang 1 Cifuentes, Diego 1 Demmel, James Weldon 1 Ding, Ounan 1 Druinsky, Alex 1 Escobedo, Adolfo R. 1 Fornstedt, Torgny 1 Forssén, Patrik 1 Fourie, Dehann 1 Grigori, Laura 1 Grip, Niklas 1 Gulliksson, Mårten E. 1 Hespanha, João Pedro 1 Hu, Yifan 1 Kaess, Michael 1 Ke, Rihuan 1 Koppenol-Gonzalez, Gabriela V. 1 Koppenol, Daniël C. 1 Lin, Guangliang 1 Lin, Lin 1 Lourenco, Christopher J. 1 Moreno-Centeno, Erick 1 Natarajan, E. Palamadai 1 Ng, Michael Kwok-Po 1 Niessen, Frank B. 1 Palamadai Natarajan, Ekanathan 1 Parrilo, Pablo A. 1 Pfander, Götz E. 1 Ploskas, Nikolaos 1 Ranka, Sanjay 1 Sahinidis, Nikolaos V. 1 Samaras, Nikolaos 1 Schenk, Olaf 1 Schroeder, Craig 1 Scott, Jennifer A. 1 Sethian, James A. 1 Shklarski, Gil 1 Sid-Lakhdar, Wissam M. 1 Sun, Xiaobai 1 Terán Espinoza, Antonio 1 Trivedi, Kishor Shridharbhai 1 Van der Vorst, Henk Albertus 1 van Zuijlen, Paul P. M. 1 Vermolen, Fred J. 1 Vuik, Cornelis 1 Wei, Ting 1 Wilkening, Jon A. 1 Yeralan, Sencer Nuri 1 Zhang, Ye all top 5 Referenced in 16 Serials 7 ACM Transactions on Mathematical Software 3 Numerical Linear Algebra with Applications 2 Journal of Computational Physics 2 SIAM Journal on Matrix Analysis and Applications 2 Linear Algebra and its Applications 2 Mathematical Programming. Series A. Series B 2 SIAM Journal on Scientific Computing 2 Mathematical Programming Computation 1 Computer Methods in Applied Mechanics and Engineering 1 Inverse Problems 1 Journal of Mathematical Biology 1 Mathematics of Computation 1 SIAM Journal on Discrete Mathematics 1 ETNA. Electronic Transactions on Numerical Analysis 1 GAMM-Mitteilungen 1 SpringerBriefs in Mathematics all top 5 Referenced in 17 Fields 27 Numerical analysis (65-XX) 6 Operations research, mathematical programming (90-XX) 4 Combinatorics (05-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 4 Probability theory and stochastic processes (60-XX) 4 Computer science (68-XX) 3 Partial differential equations (35-XX) 2 Statistics (62-XX) 2 Mechanics of deformable solids (74-XX) 2 Fluid mechanics (76-XX) 2 Information and communication theory, circuits (94-XX) 1 Commutative algebra (13-XX) 1 Ordinary differential equations (34-XX) 1 Operator theory (47-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Optics, electromagnetic theory (78-XX) 1 Biology and other natural sciences (92-XX) Referencing Publications by Year