Questions tagged [sparse-matrix]
Questions related to storage, assembly, operations, and other aspects of dealing with sparse matrices, for which only non-zero elements are stored. Questions that do not with sparse matrices directly, but other means of using sparsity should be tagged with [sparse-operator].
311
questions
58
votes
4
answers
9k
views
What guidelines should I follow when choosing a sparse linear system solver?
Sparse linear systems turn up with increasing frequency in applications. One has a lot of routines to choose from for solving these systems. At the highest level, there is a watershed between direct (...
- 3,115
33
votes
6
answers
32k
views
What is the fastest way to calculate the largest eigenvalue of a general matrix?
EDIT: I am testing if any eigenvalues have a magnitude of one or greater.
I need to find the largest absolute eigenvalue of a large sparse, non-symmetric matrix.
I have been using R's ...
- 501
25
votes
3
answers
905
views
Solving $(G^TA^{-1}G)x = b$ without inverting $A$
I have matrices $A$ and $G$. $A$ is sparse and is $n\times n$ with $n$ very large (can be on the order of several million.) $G$ is an $n\times m$ tall matrix with $m$ rather small ($1 \lt m \lt 1000$) ...
- 1,320
18
votes
5
answers
8k
views
What is the best way to determine the number of non zeros in sparse matrix multiplication?
I was wondering whether there is a fast and efficient method to find the number of non zeros in advance for sparse matrix multiplication operation assuming both matrices are in CSC or CSR format.
I ...
- 333
18
votes
6
answers
2k
views
How to reorder variables to produce a banded matrix of minimum bandwidth?
I'm trying to solve a 2D Poisson equation by finite differences. In the process, I obtain a sparse matrix with only $5$ variables in each equation. For example, if the variables were $U$, then the ...
- 11.9k
18
votes
5
answers
779
views
20% performance penalty for a nice software design
I'm writing a small library for sparse matrix computations as a way to teach myself to make the best use of object-oriented programming. I've worked really hard on having a nice object model, where ...
- 9,168
16
votes
1
answer
4k
views
Why does SciPy eigsh() produce erroneous eigenvalues in case of harmonic oscillator?
I'm developing some larger code to perform eigenvalue computations of huge sparse matrices, in the context of computational physics. I test my routines against the simple harmonic oscillator in one ...
- 974
14
votes
2
answers
6k
views
Compute all eigenvalues of a very big and very sparse adjacency matrix
I have two graphs with nearly n~100000 nodes each. In both graphs, each node is connected to exactly 3 other nodes so the adjacency matrix is symmetric and very sparse.
The hard part is I need all ...
- 243
13
votes
3
answers
4k
views
Rule of thumb for sparse vs dense matrix storage
Suppose I know the expected sparsity of a matrix (i.e. the number of non-zeros / total possible number of non-zeros). Is there a rule of thumb (perhaps approximate) for deciding whether to use sparse ...
- 143
13
votes
3
answers
5k
views
Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system
I am wondering if the Thomas algorithm is the fastest way (provably?) to solve a symmetric diagonally dominate sparse tridiagonal system in terms of algorithmic complexity (not looking for ...
- 1,859
12
votes
4
answers
6k
views
What are the best Python packages/interfaces to sparse direct solvers?
Please list the Python package (petsc4py, etc...) and the sparse direct solvers it supports. One (community-wiki) answer per package, please.
12
votes
3
answers
2k
views
Sparse linear solver for many right-hand sides
I need to solve the same sparse linear system (300x300 to 1000x1000) with many right hand sides (300 to 1000).
In addition to this first problem, I would also like to solve different systems, but with ...
- 353
11
votes
3
answers
3k
views
What is the overhead in sparse matrix multiplication
Does matrix multiplication (both Mat*Mat, and Mat*Vec) scale with number of non-zeros, or with the size of the matrix? Or some combination of the two.
What about with shape.
For example, I have a ...
- 1,155
11
votes
1
answer
5k
views
How to compute Singular value decomposition of a large matrix with Python
Language: Python3
Problem: I have a matrix Q of shape [51200 rows x 51200 cols] stored in a binary file, each of the element in this matrix has a data type of complex64. To load the data into memory I ...
- 111
10
votes
5
answers
11k
views
Best choice of solver for a large sparse symmetric (but not positive definite) system
I am presently working on solving very large symmetric (but not positive definite) systems, generated by some certain algorithms. These matrices have a nice block sparsity which can be used for ...
- 131
10
votes
2
answers
6k
views
How to efficiently implement Dirichlet boundary conditions in global sparse finite element stiffnes matrices
I am wondering how Dirichlet boundary conditions in global sparse finite element matrices are actually implemented efficiently. For example lets say that our global finite element matrix was:
$$K =
\...
- 1,859
10
votes
1
answer
1k
views
Why SVD is talk about less than QR and LU for sparse matrix?
For example the C++ sparse matrix libraries I used -- Eigen and SuiteSparse, they seem not to have any SVD funcitionality for sparse matrix. So just curious, is SVD more difficult than QR/LU for ...
- 201
10
votes
2
answers
590
views
Which novel data structures are used in adaptive FEM?
A lot of adaptive FEM libraries use more advanced mesh data structures to handle adding/removing nodes, edges, triangles, tetrahedra, etc. For example, the p4est library uses octree data structures ...
- 9,168
10
votes
1
answer
1k
views
Does PETSc ever make use of LAPACK libraries for sparse matrix math?
Does compiling PETSc with an external BLAS/LAPACK library significantly affect performance on sparse matrices, or does it only use those libraries for dense matrix math?
- 3,345
10
votes
4
answers
550
views
Are there any quad-double arithmetic sparse matrix package?
I am working on some ill-conditioned large sparse linear system of equations. I want to use double-double arithmetic or quad-double arithmetic to solve them. I know that there is a package named MPACK ...
- 191
9
votes
3
answers
5k
views
Solving a sparse and highly ill-conditioned system
I intend to solve Ax = b where A is complex, sparse, unsymmetric and highly ill-conditioned (condition number ~ 1E+20) square or rectangular matrix. I have been able to solve the system with ZGELSS in ...
- 167
9
votes
2
answers
2k
views
Solving Lx = b for big sparse Laplacian matrices
What algorithm is more practically suited in terms of performance for solving the $\mathbf{Lx=b}$ equation, where $\mathbf{L}$ is a generic Laplacian matrix (associated to a strongly connected graph, ...
- 193
9
votes
2
answers
7k
views
Integer operations vs floating point operations
I have been working with an algorithm, which uses
additions of floating point vectors,
(sparse matrix of floats)x(dense vector of floats) dot products
I recently found out that I can get the same ...
9
votes
3
answers
4k
views
Calculating the log-determinant of a large sparse matrix
I need to calculate $\log(\det (\mathbf M_i))$ where the $\mathbf M_i$'s are large sparse matrices, which are real, symmetric and positive semi-definite. I hope to have between $10$ and $100$ of ...
- 257
9
votes
4
answers
1k
views
Sparse matrix implementation of the Kalman Filter?
I have a Kalman Filter based modelling code that I have developed for a near-real time regional ionospheric mapping application. The code assimilates data from different sensors into a map (described ...
- 287
9
votes
1
answer
477
views
Solving a system with a small rank diagonal update
Suppose I have the original large, sparse linear system: $A\textbf{x}_0=\textbf{b}_0$. Now, I do not have $A^{-1}$ as A is too large to factor or any sort of decomposition of $A$, but assume that I ...
- 1,320
9
votes
3
answers
610
views
Computing the characteristic polynomial of real sparse matrix
Given a generic sparse matrix $A \in \mathbb{R}^{n\times n}$ with m << n (correction: $m \ll n^2$) non-zero elements (typically $m \in {\cal O}(n)$). $A$ is generic in the sense that it has no ...
user182
8
votes
3
answers
862
views
Solving shifted linear systems with LU factorization
I am interested in solving a sequence of shifted linear systems $(A+\sigma I)x = b$ for various values of $\sigma$. The matrix $A$ is sparse and not too large, so I have its LU factorization available....
- 4,460
8
votes
2
answers
1k
views
Taxonomy of ILU preconditioners
I learned that for BiCGStab solver for sparse linear systems it's pretty much always necessary to use a preconditioner. I realized by now that choosing a good one is problem dependent.
Surfing the ...
- 1,393
8
votes
2
answers
1k
views
How does a Sparse Direct Solver know about dimensionality of a problem being solved?
It is claimed that the time and memory complexities of sparse direct solver are $O(N^2)$ and $O(N^{4/3})$ for 3D problems and $O(N^{1.5})$ and $O(N \log N)$ for 2D, respectively.
But how does a ...
- 1,111
8
votes
1
answer
6k
views
How to use Lanczos method to compute eigenvalues and eigenvectors
I have a sparse and symmetric matrix A(n x n). The method Lanczos tranforms matrix A into tridiagonal and symmetric matrix T and the Lanczos vectors in matrix V.
From there how do I compute k ...
- 121
8
votes
1
answer
9k
views
Which C++ linear algebra library is probably the fastest on solving huge sparse [square matrix] linear system?
I am developing a 2D CFD solver for fluid-particle interaction. To solve Navier-Stokes equations on a grid of size $10000\times 10000$ cells (or >1 million cells), a large linear system $Ax=b$ with $A$...
- 223
8
votes
3
answers
3k
views
Solving a non-symmetric non-diagonally dominant sparse system the best way
I faintly recall from my early "numerics" lectures that iterative linear solvers for $Ax=b$ often require that when $A$ is decomposed as
$$A=D + M$$
where D is a diagonal matrix and $M$ has zero ...
- 487
8
votes
1
answer
488
views
bit-packing and compression of data structures in scientific computing
I recently came across this paper, which describes a scheme for saving memory in representing sparse matrices. A 32-bit integer can store numbers up to ~4 billion. But when you solve a PDE you've gone ...
- 9,168
8
votes
5
answers
3k
views
Good Finite Element Library for a small project
I'm currently working on this project and I have a basic structural analyzer that uses the finite element method. Essentially, I turn each block into a set of trusses, construct a stiffness matrix ...
- 123
8
votes
1
answer
2k
views
How to get sparse complex matrices from my code to PETSc efficiently
What is the most efficient way to get a complex sparse matrix from my Fortran code to PETSc? I understand that this is problem dependent, so I tried to give as many relevant details as possible below.
...
- 2,920
8
votes
2
answers
4k
views
When is it easy to invert a sparse matrix?
(Crossposted on cstheory.SE)
When is it easy to invert a sparse matrix? Specifically, I'm wondering about the cases in which matrix inversion has similar cost to sparse matrix multiplication, hence ...
- 1,869
8
votes
2
answers
302
views
calculating eigenvector components of a given vector
I have some vector $V$ which can be decomposed into the eigenspace of the hermitian sparse operator $M$:
$V = \sum_i v_i \hat{m}_i$
Is there a way to find the $\hat{m}_i$ (the eigenvector itself) ...
- 1,155
7
votes
2
answers
1k
views
Why does sparse linear algebra have a low arithmetic intensity?
I often see the terms "low arithmetic intensity" and "memory-bound" associated with sparse matrix operations. However, my intuition is that a sparse matrix operation should be less memory-bound, if ...
- 98
7
votes
2
answers
505
views
Is there an iterative solver for dense matrices with possible zero diagonal entries?
Is there an iterative solver that can handle potentially zero entries on the central diagonal? I am implementing a polynomial fitting algorithm (up to $10^{th}$-order) and my matrix is a "...
- 213
7
votes
4
answers
3k
views
computing the determinant of a dense nonsymmetric 100x100 matrix having very big and very small eigenvalues
The motivation for my question is the following: in one of Project Euler questions there is a need to count the spanning trees of a rectangular grid graph of dimension 100x500. By the Matrix-Tree ...
- 223
7
votes
3
answers
2k
views
How to compute the rank of a large sparse matrix in MATLAB
I am interested in computing the ranks of fairly large, the largest being of magnitude $10^6$ x $10^6$, sparse matrices whose entires are all 0, 1, or -1. I have been trying to use Matlab to ...
- 171
7
votes
2
answers
451
views
Block-matrix: optimal fill-in reduction for LU factorization
Consider a square $N \times N$ block-matrix $\mathbf{A}$, where each $n \times n$ block $\mathbf{A}_{ii}$ is either a dense block or a zero-block. So, $N$ denotes the number of blocks, $n$ denotes the ...
- 8,572
7
votes
5
answers
12k
views
How to solve block tridiagonal matrix using Thomas algorithm
Thomas algorithm can be used to solve a tridiagonal matrix:
$$
\begin{bmatrix}
{b_ 1} & {c_ 1} & { } & { } & { 0 } \\
{a_ 2} & {b_ 2} & {c_ 2} & { } & { }...
- 345
7
votes
1
answer
649
views
Efficient algorithm for solving linear system with symmetric near-tridiagonal matrix?
I would like to solve the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$, with
$$\mathbf{A}=\mathbf{T}+\mathbf{C}$$
where $\mathbf{T}$ is a symmetric tridiagonal matrix and $\mathbf{C}$ is a corner-...
- 489
7
votes
2
answers
3k
views
Sparse Incomplete Cholesky
I'm looking for an efficient, multicore, library to do incomplete cholesky (possibly modified). Many ILU code exists, but I can't find much about IC except in PETSC or Pastix. Could some of you drop ...
- 455
7
votes
1
answer
1k
views
Sparse hermitian eigensystems: are there better techniques than Arpack or TRLan?
As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
- 240
7
votes
0
answers
124
views
Can we sparse solve a few eigenvalues specified by index range?
I need to solve a few eigenvalues of a large sparse matrix specified by their index range. These indices are according to the whole eigenspectrum sorted in algebraic (not absolute value) ascending ...
- 303
7
votes
1
answer
299
views
Choice of iterative solver for a sparse asymmetric matrix with symmetric structure
I have a sparse $n\times n$ matrix $A$ with a pretty interesting structure. It has a block structure with a symmetric structure but asymmetric blocks. Expressed mathematically the block $A_{jk} = A_{...
- 2,059
7
votes
0
answers
321
views
Compute sparsity pattern of $A^2$
Suppose we have a sparse matrix $A$. Is there any way to compute just the sparsity pattern of $A^2 = A \cdot A$ (I do not actually need to know what exactly the nonzero value are) faster than to ...
- 71