Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems

DOI10.1137/16M1077398zbMath1367.65041arXiv1605.09148OpenAlexW3105227640WikidataQ114074328 ScholiaQ114074328MaRDI QIDQ5270418

Paul Van Dooren, Jean-Charles Delvenne, Michael T. Schaub, Maguy Trefois

Publication date: 23 June 2017

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.09148

zbMATH Keywords

linear systemiterative algorithmsconjugate gradientsLaplacian matrixmatrix factorizationsparsityhierarchical matricesminimal norm solution

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Iterative numerical methods for linear systems (65F10) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Decomposition in multidimensional Boolean-optimization problems with sparse matrices, Unnamed Item

Uses Software

• CSparse

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A randomized Kaczmarz algorithm with exponential convergence
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• Construction and arithmetics of \(\mathcal H\)-matrices
• Introduction to hierarchical matrices with applications.
• An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
• Hierarchical Matrices: Algorithms and Analysis
• Krylov Subspace Methods for Linear Systems with Tensor Product Structure
• Direct Methods for Sparse Linear Systems
• Randomized Iterative Methods for Linear Systems
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Solution of Linear Systems and Matrix Inversion in the TT-Format
• A projection method to solve linear systems in tensor format
• Using petal-decompositions to build a low stretch spanning tree
• Approaching Optimality for Solving SDD Linear Systems
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• A bibliography on semiseparable matrices