Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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].

Filter by
Sorted by
Tagged with
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 (...
J. M.'s user avatar
  • 3,135
35 votes
6 answers
34k 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 ...
power's user avatar
  • 521
25 votes
3 answers
924 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$) ...
Costis's user avatar
  • 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 ...
Recker's user avatar
  • 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 ...
Paul's user avatar
  • 12k
18 votes
5 answers
791 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 ...
Daniel Shapero's user avatar
16 votes
2 answers
7k 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 ...
Mahdi's user avatar
  • 263
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 ...
seb's user avatar
  • 994
15 votes
3 answers
5k 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 ...
josh_eime's user avatar
  • 163
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 ...
James's user avatar
  • 1,909
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
3k 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 ...
nat chouf's user avatar
  • 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 ...
Andrew Spott's user avatar
  • 1,155
11 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 = \...
James's user avatar
  • 1,909
11 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 ...
user5302's user avatar
  • 211
11 votes
1 answer
8k 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 ...
SAM's user avatar
  • 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 ...
Soumya's user avatar
  • 131
10 votes
2 answers
9k 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 ...
Dionysios Georgiadis's user avatar
10 votes
1 answer
12k 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$...
KOF's user avatar
  • 243
10 votes
2 answers
615 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 ...
Daniel Shapero's user avatar
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?
Dan's user avatar
  • 3,355
10 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 ...
yohbs's user avatar
  • 267
10 votes
4 answers
581 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 ...
Hanyu Ye's user avatar
  • 191
9 votes
3 answers
6k 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 ...
user1234's user avatar
  • 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, ...
teodron's user avatar
  • 193
9 votes
1 answer
7k 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 ...
HongTu's user avatar
  • 131
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 ...
Bogdanovist's user avatar
9 votes
2 answers
5k 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 ...
Yaroslav Bulatov's user avatar
9 votes
1 answer
521 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 ...
Costis's user avatar
  • 1,320
8 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 ...
Sam Hatfield's user avatar
8 votes
3 answers
916 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....
Victor Liu's user avatar
  • 4,480
8 votes
2 answers
705 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 "...
niran90's user avatar
  • 233
8 votes
2 answers
2k 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 ...
Johntra Volta's user avatar
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 ...
Alexander's user avatar
  • 1,111
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 ...
Lagerbaer's user avatar
  • 487
8 votes
1 answer
522 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 ...
Daniel Shapero's user avatar
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 ...
Chris Conlon's user avatar
8 votes
1 answer
3k 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. ...
Ondřej Čertík's user avatar
8 votes
3 answers
651 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 ...
user avatar
8 votes
2 answers
314 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) ...
Andrew Spott's user avatar
  • 1,155
7 votes
3 answers
1k views

How large is large for direct solvers?

Let us say I want to solve a large sparse linear system. It is said that iterative solvers should be better than direct solvers in this case. But how large is large? What is the exact threshold beyond ...
timur's user avatar
  • 181
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 ...
John Donn's user avatar
  • 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 ...
jemmy.bruce's user avatar
7 votes
2 answers
618 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 ...
Anton Menshov's user avatar
  • 8,672
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} & { } & { }...
xslittlegrass's user avatar
7 votes
1 answer
670 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-...
Arturo don Juan's user avatar
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 ...
Tom's user avatar
  • 465
7 votes
2 answers
435 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_{...
EMP's user avatar
  • 2,089
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 ...
Misha's user avatar
  • 230
7 votes
0 answers
137 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 ...
xiaohuamao's user avatar

1
2 3 4 5
7