The Use of Linear Graphs in Gauss Elimination
Seymour V. Parter · SIAM Review · 1961
Previous article Next article The Use of Linear Graphs in Gauss EliminationS. ParterS. Parterhttps://doi.org/10.1137/1003021PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] S. D. Conte and , R. T. Dames, An alternating direction method for solving the biharmonic equation, Math. Tables Aids Comput., 12 (1958), 198–205 MR0105813 0083.12304 CrossrefGoogle Scholar[2] Elizabeth H. Cuthill and , Richard S. Varga, A method of normalized block iteration, J. Assoc. Comput. Mach., 6 (1959), 236–244 MR0117877 0088.09403 CrossrefISIGoogle Scholar[3] K. Friedrich, Beitrüge zur direkten and indirekten Auflosung der Normalgleichungen unter besonderer Beriicksichtigung der geodätischen Netzausgleichung, Zeitsehrift für Vermessungswesen, 59 (1930), 461–469, 525–539, 671–697 Google Scholar[4] Robert D. Richtmyer, Difference methods for initial-value problems, Interscience tracts in pure and applied mathematics. Iract 4, Interscience Publishers, Inc., New. York, 1957xii+238 MR0093918 0079.33702 Google Scholar[5] R. S. Varga, Factorization and normalized iterative methods, Report, WAPD T-950, West. Elec. Corp., 1959, April Google Scholar Previous article Next article FiguresRelatedReferencesCited byDetails Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structureJournal of Symbolic Computation, Vol. 116 Cross Ref Interconnected Hierarchical Structures for Fast Direct Elliptic Solution26 February 2022 | Journal of Scientific Computing, Vol. 91, No. 1 Cross Ref Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky FactorizationsChristopher J. Lourenco and Erick Moreno-Centeno14 March 2022 | SIAM Journal on Matrix Analysis and Applications, Vol. 43, No. 1AbstractPDF (1350 KB)EXAGRAPH: Graph and combinatorial methods for enabling exascale applications30 September 2021 | The International Journal of High Performance Computing Applications, Vol. 35, No. 6 Cross Ref Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs11 April 2021 | Algorithmica, Vol. 83, No. 7 Cross Ref Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion25 May 2020 | Mathematical Programming, Vol. 188, No. 1 Cross Ref A fast direct solver for nonlocal operators in wavelet coordinatesJournal of Computational Physics, Vol. 428 Cross Ref Chordal graphs in triangular decomposition in top-down styleJournal of Symbolic Computation, Vol. 102 Cross Ref On the Chordality of Simple Decomposition in Top-Down Style18 March 2020 Cross Ref Graph-Based Locality-Sensitive Circuit Sketch RecognizerIEEE Access, Vol. 8 Cross Ref Symbolic Factorization Re-utilization for Contingency Analysis Cross Ref Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low TreewidthACM Transactions on Algorithms, Vol. 14, No. 3 Cross Ref Multiplicity adjustment for temporal and spatial scan statistics using Markov property25 May 2018 | Japanese Journal of Statistics and Data Science, Vol. 1, No. 1 Cross Ref Decomposition in Multidimensional Boolean-Optimization Problems with Sparse Matrices2 March 2018 | Journal of Computer and Systems Sciences International, Vol. 57, No. 1 Cross Ref Enabling massive deep neural networks with the GraphBLAS Cross Ref Thinning a Triangulation of a Bayesian Network or Undirected Graph to Create a Minimal TriangulationInternational Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, Vol. 25, No. 03 Cross Ref Search-space size in contraction hierarchiesTheoretical Computer Science, Vol. 645 Cross Ref A survey of direct methods for sparse linear systems23 May 2016 | Acta Numerica, Vol. 25 Cross Ref Multi-core parallel robust structured multifrontal factorization method for large discretized PDEsJournal of Computational and Applied Mathematics, Vol. 296 Cross Ref Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach18 August 2016 | SIAM Journal on Discrete Mathematics, Vol. 30, No. 3AbstractPDF (1644 KB)Route Planning in Transportation Networks11 November 2016 Cross Ref A scalable distributed graph partitionerProceedings of the VLDB Endowment, Vol. 8, No. 12 Cross Ref Modifying a Graph Using Vertex Elimination8 November 2013 | Algorithmica, Vol. 72, No. 1 Cross Ref Large Induced Subgraphs via Triangulations and CMSO12 February 2015 | SIAM Journal on Computing, Vol. 44, No. 1AbstractPDF (738 KB)Direct Methods for Linear Systems7 October 2014 Cross Ref Graphical Models and Message-Passing Algorithms: Some Introductory Lectures Cross Ref Graph Fill-In, Elimination Ordering, Nested Dissection and Contraction Hierarchies12 January 2016 Cross Ref Searching for better fill-inJournal of Computer and System Sciences, Vol. 80, No. 7 Cross Ref References5 September 2014 Cross Ref Interactively Exploring the Connection between Nested Dissection Orderings for Parallel Cholesky Factorization and Vertex Separators Cross Ref Performance models and workload distribution algorithms for optimizing a hybrid CPU–GPU multifrontal solverComputers & Mathematics with Applications, Vol. 67, No. 7 Cross Ref Ordering for Optimal Patterns of Structural Matrices: Graph Theory Methods7 November 2013 Cross Ref On sparse matrix orderings in interior point methods8 November 2013 | Optimization and Engineering, Vol. 14, No. 4 Cross Ref An efficient block variant of robust structured multifrontal factorization method29 August 2013 | Chinese Physics B, Vol. 22, No. 8 Cross Ref Adaptive AMG with coarsening based on compatible weighted matching17 September 2014 | Computing and Visualization in Science, Vol. 16, No. 2 Cross Ref Efficient Structured Multifrontal Factorization for General Large Sparse Matrices21 March 2013 | SIAM Journal on Scientific Computing, Vol. 35, No. 2AbstractPDF (1216 KB)Randomized Sparse Direct Solvers21 March 2013 | SIAM Journal on Matrix Analysis and Applications, Vol. 34, No. 1AbstractPDF (587 KB)Subexponential Parameterized Algorithm for Minimum Fill-In5 December 2013 | SIAM Journal on Computing, Vol. 42, No. 6AbstractPDF (520 KB)Modeling Morphogenesis in Multicellular Structures with Cell Complexes and L-systems5 August 2012 Cross Ref Search-Space Size in Contraction Hierarchies Cross Ref Benchmarking ordering techniques for nonserial dynamic programming22 June 2012 | Memetic Computing, Vol. 4, No. 3 Cross Ref Fast time domain simulation of power systems using multilevel preconditioners with adaptive reconstruction strategiesSimulation Modelling Practice and Theory, Vol. 25 Cross Ref Treewidth computation and extremal combinatorics7 June 2012 | Combinatorica, Vol. 32, No. 3 Cross Ref Finding Induced Paths of Given Parity in Claw-Free Graphs9 November 2010 | Algorithmica, Vol. 62, No. 1-2 Cross Ref Combinatorial Problems in Solving Linear Systems29 March 2012 Cross Ref Combinatorial Scientific Computing29 March 2012 Cross Ref Robust and Efficient Multifrontal Solver for Large Discretized PDEs Cross Ref How to Eliminate a Graph Cross Ref Factoring matrices with a tree-structured sparsity patternLinear Algebra and its Applications, Vol. 435, No. 5 Cross Ref Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models8 February 2011 | Machine Learning, Vol. 84, No. 3 Cross Ref A parallel sparse solver and its relation to graphs Cross Ref Comparing the similarity and spatial structure of neural representations: A pattern-component modelNeuroImage, Vol. 55, No. 4 Cross Ref A weighted reverse Cuthill–McKee procedure for finite element method algorithms to solve strongly anisotropic electrodynamic problemsJournal of Applied Physics, Vol. 109, No. 3 Cross Ref Interactively exploring elimination orderings in symbolic sparse Cholesky factorizationProcedia Computer Science, Vol. 1, No. 1 Cross Ref Dynamic programming and planarity: Improved tree-decomposition based algorithmsDiscrete Applied Mathematics, Vol. 158, No. 7 Cross Ref Minimum fill-in and treewidth of split+ke and split+kv graphsDiscrete Applied Mathematics, Vol. 158, No. 7 Cross Ref Treewidth computations I. Upper boundsInformation and Computation, Vol. 208, No. 3 Cross Ref Superfast Multifrontal Method for Large Structured Linear Systems of Equations4 December 2009 | SIAM Journal on Matrix Analysis and Applications, Vol. 31, No. 3AbstractPDF (1494 KB)A Programming Language Tailored to the Specification and Solution of Differential Equations Describing Processes on Networks Cross Ref Fast Computation of Minimal Fill Inside A Given Elimination Ordering3 December 2008 | SIAM Journal on Matrix Analysis and Applications, Vol. 30, No. 4AbstractPDF (262 KB)Graph-Based Local Elimination Algorithms in Discrete Optimization Cross Ref Developmental Computing Cross Ref Sequential and parallel triangulating algorithms for Elimination Game and new insights on Minimum DegreeTheoretical Computer Science, Vol. 409, No. 3 Cross Ref Large-scale testing of the Internet's Border Gateway Protocol (BGP) via topological scale-downACM Transactions on Modeling and Computer Simulation, Vol. 18, No. 3 Cross Ref (BP)2: Beyond pairwise Belief Propagation labeling by approximating Kikuchi free energies Cross Ref Local elimination algorithms for solving sparse discrete problems5 February 2011 | Computational Mathematics and Mathematical Physics, Vol. 48, No. 1 Cross Ref Postoptimal Analysis in Nonserial Dynamic Programming Cross Ref Local fill reduction techniques for sparse symmetric linear systems7 November 2006 | Electrical Engineering, Vol. 89, No. 8 Cross Ref Reminiscences related to graph theoryComputer Science Review, Vol. 1, No. 1 Cross Ref Tree decomposition and discrete optimization problems: A surveyCybernetics and Systems Analysis, Vol. 43, No. 4 Cross Ref Numerical Methods for Transport-Resistance Source–Sink Allocation Models Cross Ref Combinatorial algorithms enabling computational science: tales from the front20 September 2006 | Journal of Physics: Conference Series, Vol. 46 Cross Ref The elimination procedure for the competition number is not optimalDiscrete Applied Mathematics, Vol. 154, No. 11 Cross Ref Lex M versus MCS-MDiscrete Mathematics, Vol. 306, No. 3 Cross Ref Minimal triangulations of graphs: A surveyDiscrete Mathematics, Vol. 306, No. 3 Cross Ref Minimal fill in O(n2.69) timeDiscrete Mathematics, Vol. 306, No. 3 Cross Ref Effective Preconditioning through Ordering Interleaved with Incomplete Factorization31 July 2006 | SIAM Journal on Matrix Analysis and Applications, Vol. 27, No. 4AbstractPDF (271 KB)A wide-range algorithm for minimal triangulation from an arbitrary orderingJournal of Algorithms, Vol. 58, No. 1 Cross Ref Robust algorithm for random resistor networks using hierarchical domain structureJournal of Computational Physics, Vol. 211, No. 2 Cross Ref Simple and Efficient Modifications of Elimination Orderings Cross Ref A class of novel parallel algorithms for the solution of tridiagonal systemsParallel Computing, Vol. 31, No. 6 Cross Ref Perfect Gaussian Elimination Cross Ref Algebraic elimination of slide surface constraints in implicit structural analysis1 January 2003 | International Journal for Numerical Methods in Engineering, Vol. 57, No. 8 Cross Ref The Minimum Degree Heuristic and the Minimal Triangulation Process Cross Ref Maximum Cardinality Search for Computing Minimal Triangulations28 February 2003 Cross Ref A unifying graph model for designing parallel algorithms for tridiagonal systemsParallel Computing, Vol. 27, No. 7 Cross Ref Numerical linear algebra algorithms and software Cross Ref Numerical linear algebra algorithms and softwareJournal of Computational and Applied Mathematics, Vol. 123, No. 1-2 Cross Ref Towards a scalable hybrid sparse solver1 January 2000 | Concurrency: Practice and Experience, Vol. 12, No. 2-3 Cross Ref Towards a scalable hybrid sparse solver1 January 2000 | Concurrency: Practice and Experience, Vol. 12, No. 2-3 Cross Ref Gaussian elimination for the solution of linear systems of equations Cross Ref Probabilistic Networks Cross Ref Performance of Greedy Ordering Heuristics for Sparse Cholesky Factorization1 August 2006 | SIAM Journal on Matrix Analysis and Applications, Vol. 20, No. 4AbstractPDF (275 KB)A graph-theoretic approach to queueing analysis part i: theoryCommunications in Statistics. Stochastic Models, Vol. 15, No. 5 Cross Ref Generic Graph Algorithms for Sparse Matrix Ordering Cross Ref References Cross Ref An Object-Oriented Collection of Minimum Degree Algorithms15 August 2002 Cross Ref Experimental study of ILU preconditioners for indefinite matricesJournal of Computational and Applied Mathematics, Vol. 86, No. 2 Cross Ref Parallel sparse Cholesky factorization8 June 2005 Cross Ref On the pressure and flow-rate distributions in tree-like and arterial-venous networksBulletin of Mathematical Biology, Vol. 58, No. 4 Cross Ref On Linear Recognition of Tree-Width at Most Four1 August 2006 | SIAM Journal on Discrete Mathematics, Vol. 9, No. 1AbstractPDF (2125 KB)Weighted graph based ordering techniques for preconditioned conjugate gradient methodsBIT Numerical Mathematics, Vol. 35, No. 1 Cross Ref BIONNIC: An Efficient and Flexible Integrator for Biological Neural Network Simulators Cross Ref Realizations of interlacing by tree-patterned matricsLinear and Multilinear Algebra, Vol. 38, No. 1-2 Cross Ref Predicting Structure in Sparse Matrix Computations31 July 2006 | SIAM Journal on Matrix Analysis and Applications, Vol. 15, No. 1AbstractPDF (2174 KB)Generalized and Sparse Least Squares Problems Cross Ref Cutting down on Fill Using Nested Dissection: Provably Good Elimination Orderings Cross Ref Structural Representations of Schur Complements in Sparse Matrices Cross Ref Predicting Structure in Nonsymmetric Sparse Matrix Factorizations Cross Ref A comparative study of algorithms for reducing the fill-in during Cholesky factorizationBulletin Géodésique, Vol. 66, No. 3 Cross Ref Towards a cost-effective ILU preconditioner with high level fillBIT, Vol. 32, No. 3 Cross Ref Preconditioned conjugate gradient methods for the incompressible Navier-Stokes equationsInternational Journal for Numerical Methods in Fluids, Vol. 15, No. 3 Cross Ref Ordering Methods for Preconditioned Conjugate Gradient Methods Applied to Unstructured Grid Problems17 July 2006 | SIAM Journal on Matrix Analysis and Applications, Vol. 13, No. 3AbstractPDF (2081 KB)Parallel Algorithms for Sparse Linear Systems18 July 2006 | SIAM Review, Vol. 33, No. 3AbstractPDF (5356 KB)Colouring the discretization graphs arising in the multigrid methodComputers & Mathematics with Applications, Vol. 22, No. 7 Cross Ref Parallel symbolic factorization of sparse linear systemsParallel Computing, Vol. 14, No. 2 Cross Ref Probabilistic simulation for reliability analysis of CMOS VLSI circuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 9, No. 4 Cross Ref Iterative methods for cyclically reduced nonselfadjoint linear systems1 January 1990 | Mathematics of Computation, Vol. 54, No. 190 Cross Ref On the Performance of the Minimum Degree Ordering for Gaussian Elimination17 July 2006 | SIAM Journal on Matrix Analysis and Applications, Vol. 11, No. 1AbstractPDF (723 KB)Solution of sparse positive definite systems on a hypercube* *Research was supported by the Applied Mathematical Sciences Research Program of the Office of Energy Research, U.S. Department of Energy, and by the Canadian Natural Sciences and Engineering Research Council under grant A5509. Cross Ref Data Parallel Supercomputing Cross Ref Solution of sparse positive definite systems on a hypercubeJournal of Computational and Applied Mathematics, Vol. 27, No. 1-2 Cross Ref A direct active set algorithm for large sparse quadratic programs with simple boundsMathematical Programming, Vol. 45, No. 1-3 Cross Ref The Ranks of Extremal Positive Semidefinite Matrices with Given Sparsity Pattern17 July 2006 | SIAM Journal on Matrix Analysis and Applications, Vol. 10, No. 3AbstractPDF (1703 KB)Algorithmique et calculs de complexit� pour un solveur de type dissections embo�t�esNumerische Mathematik, Vol. 55, No. 4 Cross Ref Solution of sparse systems of equations on multiprocessor architectures2 October 2006 Cross Ref Solution of Sparse Systems of Equations on Multiprocessor Architectures Cross Ref The Direct Solution of Weighted and Equality Constrained Least-Squares Problems13 July 2006 | SIAM Journal on Scientific and Statistical Computing, Vol. 9, No. 4AbstractPDF (1279 KB)A Tree Model for Sparse Symmetric Indefinite Matrix Factorization17 July 2006 | SIAM Journal on Matrix Analysis and Applications, Vol. 9, No. 1AbstractPDF (1696 KB)The General Minimum Fill-In ProblemH. Wendel17 July 2006 | SIAM Journal on Algebraic Discrete Methods, Vol. 8, No. 4AbstractPDF (4080 KB)Inherited Matrix Entries: Principal Submatrices of the InverseWayne W. Barrett, Charles R. Johnson, D. D. Olesky, and P. van den Driessche17 July 2006 | SIAM Journal on Algebraic Discrete Methods, Vol. 8, No. 3AbstractPDF (1249 KB)Solving Tridiagonal Systems on Ensemble Architectures14 July 2006 | SIAM Journal on Scientific and Statistical Computing, Vol. 8, No. 3AbstractPDF (4496 KB)Optimal pivot strategies for load-flow calculationInternational Journal of Electrical Power & Energy Systems, Vol. 9, No. 2 Cross Ref Sparse matrices, and the estimation of variance components by likelihood methodsCommunications in Statistics - and Computation, Vol. 16, No. 2 Cross Ref The of Algebra in Computing Cross Ref The analysis of a Mathematik, Vol. No. 4 Cross Ref A for Cholesky using elimination Transactions on Mathematical Vol. 12, No. 2 Cross Ref de complexit� de Mathematik, Vol. No. 2 Cross Ref zur Cross Ref Parallel algorithms for sparse symmetric Computing, Vol. 1, No. 1 Cross Ref algorithm for sparse in Engineering Vol. No. 3 Cross Ref graphs and April 2009 | Journal of the Mathematical Mathematics and Vol. No. 1 Cross Ref Some of graph to analysis and Transactions on Circuits and Systems, Vol. 31, No. 1 Cross Ref Direct Methods for Solving Equations Cross Ref References Cross Ref of the of the and in Engineering Vol. No. 1 Cross Ref The ordering of tree & Vol. No. 4 Cross Ref A graph model for December Cross Ref A Data Structure for Parallel Transactions on Vol. No. 3 Cross Ref matrices and Algebra and its Applications, Vol. Cross Ref and August 2006 | SIAM Journal on Computing, Vol. 10, No. 2AbstractPDF Dissection Algorithm for Problems17 July 2006 | SIAM Journal on Numerical Analysis, Vol. No. 6AbstractPDF KB)A fast algorithm for solving systems of linear equations with Algebra and its Applications, Vol. Cross Ref On symbolic factorization of sparse symmetric Algebra and its Applications, Vol. Cross Ref Solution of sparse linear using Algebra and its Applications, Vol. Cross Ref A Fast of the Minimum Degree Algorithm Using Transactions on Mathematical Vol. No. 3 Cross Ref An Optimal for Symbolic Factorization of Symmetric July 2006 | SIAM Journal on Computing, Vol. 9, No. 3AbstractPDF KB)A Computation Model of Parallel Solution of Linear Transactions on Vol. No. 7 Cross Ref Algorithms and software for factorization of sparse symmetric positive definite & Vol. 11, No. 6 Cross Ref A Minimal of the Minimum Degree July 2006 | SIAM Journal on Numerical Analysis, Vol. No. 2AbstractPDF of graphs to the Gaussian elimination of Mathematics, Vol. 13, No. 2 Cross Ref Perfect Gaussian Elimination Cross Ref Algorithms and software for factorization of sparse symmetric positive definite & Vol. 10, No. 1-2 Cross Ref An Nested Dissection Algorithm for July 2006 | SIAM Journal on Numerical Analysis, Vol. 15, No. of Combinatorial August 2006 | SIAM Review, Vol. 20, No. 3AbstractPDF for Matrix and the Numerical Solution of July 2006 | SIAM Journal on Numerical Analysis, Vol. 15, No. 2AbstractPDF the of the Minimum Degree Algorithm to July 2006 | SIAM Journal on Numerical Analysis, Vol. 15, No. 1AbstractPDF competition and the of August 2006 Cross Ref An algorithm for finite element August 2006 Cross Ref An efficient algorithm for Transactions on Circuits and Systems, Vol. No. 12 Cross Ref A survey of sparse matrix of the Vol. No. 4 Cross Ref On the of the algorithm to finite element August 2006 Cross Ref Solution of linear systems of Direct methods for finite element December Cross Ref Minimal triangulation of a graph and in a sparse of Mathematical Analysis and Applications, Vol. 54, No. 3 Cross Ref A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a February 2012 | SIAM Journal on Computing, Vol. No. 1AbstractPDF of an Model for Gaussian was supported in part by and Cross Ref of the number of in with sparse symmetric Computational Mathematics and Mathematical Physics, Vol. 16, No. 5 Cross Ref On a of tridiagonal matrices by Algebra and its Applications, Vol. 8, No. 1 Cross Ref On the number of Gaussian elimination is on sparse random January | Mathematics of Computation, Vol. No. Cross Ref Nested Dissection of a July 2006 | SIAM Journal on Numerical Analysis, Vol. 10, No. 2AbstractPDF KB)A decomposition algorithm for in tree-structured Mathematics, Vol. No. 2 Cross Ref References Cross Ref A Cross Ref graphs and the elimination of Mathematical Analysis and Applications, Vol. 32, No. 3 Cross Ref Computations with Sparse July 2006 | SIAM Review, Vol. 12, No. 4AbstractPDF on sparse January | Mathematics of Computation, Vol. No. Cross Ref elimination with linear fill Cross Ref Nested graph and algorithms Cross Ref parallel sparse matrix algorithms analysis Cross Ref On methods for ordering sparse matrices in simulation Cross Ref estimation for reliability analysis of CMOS Cross Ref Combinatorial Scientific The Enabling Power of Discrete Algorithms in Computational Science Cross Ref Nonserial Dynamic Programming and Tree Decomposition in Discrete Optimization Cross Ref Minimum Fill-In and Treewidth of and Graphs Cross Ref How to Use Algorithms Cross Ref The of of Canadian Journal of Engineering, Vol. No. 5 Cross Ref Solution of Problems by Systems Transactions on Power and Systems, Vol. No. 11 Cross Ref Computer methods of of the Vol. 55, No. 11 Cross Ref Solution of a of linear equations with a sparse matrix by elimination Vol. No. 3 Cross Ref The of of Sparse Matrices and Graph July 2006 | SIAM Review, Vol. 9, No. 1AbstractPDF structural for Mathematik, Vol. No. 1 Cross Ref and Systems of July 2006 | Journal of the for and Applied Mathematics Numerical Analysis, Vol. No. 2AbstractPDF KB)A of Some Mathematical in Method of July 2006 | Journal of the for and Applied Mathematics, Vol. 11, No. 2AbstractPDF October July 2006 for and Applied & for and Applied Mathematics