Sparse Partial Pivoting in Time Proportional to Arithmetic Operations

DOI10.1137/0909058zbMath0656.65036OpenAlexW2020561008MaRDI QIDQ3804073

Tim Peierls, John R. Gilbert

Publication date: 1988

Published in: SIAM Journal on Scientific and Statistical Computing (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6623

zbMATH Keywords

LU factorizationtest problemsdepth-first searchtopological orderingsparse matrix algorithmsGaussian elimination with partial pivotingtriangular solver

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (22)

Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization ⋮ Sparse Matrix Methods for Circuit Simulation Problems ⋮ Progress in the dual simplex method for large scale LP problems: Practical dual phase 1 algorithms ⋮ The positive edge pricing rule for the dual simplex ⋮ Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky Factorizations ⋮ Parallel distributed-memory simplex for large-scale stochastic LP problems ⋮ Matrix enlarging methods and their application ⋮ Reverse-Safe Text Indexing ⋮ Design and Implementation of a Parallel Markowitz Threshold Algorithm ⋮ A survey of direct methods for sparse linear systems ⋮ Unnamed Item ⋮ Factoring matrices with a tree-structured sparsity pattern ⋮ Hyper-sparsity in the revised simplex method and how to exploit it ⋮ A direct active set algorithm for large sparse quadratic programs with simple bounds ⋮ Combinatorial Aspects in Sparse Elimination Methods ⋮ Incremental incomplete LU factorizations with applications ⋮ Sparse Gaussian Elimination Modulo p: An Update ⋮ Progress in the dual simplex algorithm for solving large scale LP problems: Techniques for a fast and stable implementation ⋮ Preconditioning of Linear Least Squares by Robust Incomplete Factorization for Implicitly Held Normal Equations ⋮ Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work ⋮ Communication Avoiding ILU0 Preconditioner ⋮ Novel update techniques for the revised simplex method

This page was built for publication: Sparse Partial Pivoting in Time Proportional to Arithmetic Operations