Fast and Efficient Parallel Solution of Sparse Linear Systems
The authors present a numerically stable parallel algorithm for a sparse \(n\times n\) symmetric positive definite linear system \(Ax = b\) that can be solved by a sequential algorithm based on the generalized nested dissection of the associated graph \(G(A)\). The algorithm is effective for systems whose associated graphs have \(s(n)\)-separator families and for which \(s(n)\)-separator trees are readily available. In such a case, the algorithm requires only \(O(\log^ 3n)\) time and \((| E| + M(s(n)))/\log n\) processors for the evaluation of the solution vector \(x = A^{-1}b\) where \(| E|\) is the number of edges in \(G(A)\) and \(M(n)\) is the number of processors sufficient for multiplying two \(n\times n\) rational matrices in time \(O(\log n)\). The algorithm is compared with previous results, and some complexity estimates are given. Some applications are also listed.
- Parallel, iterative solution of sparse linear systems: Models and architectures
- Efficient solutions of hierarchical systems of linear equations
- Parallel nested dissection for path algebra computations
- Efficient approximate solution of sparse linear systems
- A faster algorithm for solving linear algebraic equations on the star graph.
- Efficient VLSI implementation of iterative solutions to sparse linear systems
- Parallel solution of arbitrarily sparse linear systems
- Fast and efficient solution of path algebra problems
- Parallel computation of a Krylov matrix for a sparse and structured input
- A parallel implementation of the CMRH method for dense linear systems
- Maximum matchings in planar graphs via Gaussian elimination
- Additive preconditioning and aggregation in matrix computations
- Efficient parallel factorization and solution of structured and unstructured linear systems
- A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
- Parallel solution techniques for sparse linear systems in circuit simulation
- scientific article; zbMATH DE number 3862321 (Why is no real title available?)
- scientific article; zbMATH DE number 3874479 (Why is no real title available?)
- On the Complexity of Sparse Gaussian Elimination via Bordering
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- scientific article; zbMATH DE number 3967813 (Why is no real title available?)
- scientific article; zbMATH DE number 4030966 (Why is no real title available?)
- Pairwise reduction for the direct, parallel solution of sparse, unsymmetric sets of linear equations
- scientific article; zbMATH DE number 4076453 (Why is no real title available?)
- Non-standard parallel solution strategies for distributed sparse linear systems
- scientific article; zbMATH DE number 1121981 (Why is no real title available?)
- scientific article; zbMATH DE number 1163749 (Why is no real title available?)
- scientific article; zbMATH DE number 2051077 (Why is no real title available?)
- An efficient variant of gauss-jordan type algorithms for direct and parallel solution of dense linear systems
- Transformations of matrix structures work again
- scientific article; zbMATH DE number 4001308 (Why is no real title available?)
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- Processor Efficient Parallel Solution of Linear Systems of Equations
- Cache Optimized Solution for Sparse Linear System over Large Order Finite Field
- Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems
- Matrix sparsification and nested dissection over arbitrary fields
- Parallel frontal solvers for large sparse linear systems
- Minimum Cuts in Surface Graphs
- Efficient parallel computation of the characteristic polynomial of a sparse, separable matrix
- Parallel nested dissection
- Parallelism and fast solution of linear systems
- Randomized preprocessing of homogeneous linear systems of equations
This page was built for publication: Fast and Efficient Parallel Solution of Sparse Linear Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4277539)