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].
35
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
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
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
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
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
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
4
votes
4
answers
7k
views
Efficient assembly of finite element matrix in MATLAB
Question
What is the most efficient algorithm for finding a row of a matrix which matches a given row? This is the same as a table lookup based on multiple criteria.
Context
Finite Element Matrices ...
- 178
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
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
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
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
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
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
1
answer
476
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
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
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
6
votes
2
answers
329
views
Is it possible to ignore/discard part of a matrix when finding eigenvalues?
I have have multiple large matrices for which I need to find the largest absolute eigenvalue. I know that there is a large submatrix that does not vary. Is it possible to ignore/discard the submatrix?
...
- 501
6
votes
2
answers
561
views
Large-scale generalized eigenvalue problem with low rank LHS matrix
Assume that we have generalized eigenvalue problem:
$B^HB\textbf{x} = \lambda A\textbf{x}$
where $A$ is an nxn Hermitian sparse matrix (n is very large, so we do not have $A^{-1}$ but can solve ...
- 1,320
6
votes
1
answer
1k
views
Supernodal vs. Multifrontal Matrix Decompositions
Reading through Tim Davis' book Direct Methods For Sparse Linear Systems, he says that matlab can use a supernodal Cholesky decomposition but never uses a multifrontal Cholesky decomposition. At least ...
- 805
5
votes
1
answer
104
views
Is the bandwidth of indefinite A equal to its factor L in LDL^T?
In George, Liu, and Ng's book Computer Solutions of Sparse Linear Systems, it has been shown that bandwidth of $A$ is equal to bandwidth of its factors in $LL^T$.(section 4.3) However, I guess this is ...
- 245
5
votes
2
answers
550
views
How "sparse" should a sparse matrix be to see benefits?
I have a matrix, whose size scales as $2^N$ (assume even $N$). In each row of the matrix, only about $2^{N/2}$ of the entries are filled ($N$ can be somewhere between 10 and 40, depending on what's ...
- 193
5
votes
3
answers
2k
views
What is the best solver for solving a large sparse indefinite system
What's the best solver that can solve a large sparse but indefinite matrix?
- 51
5
votes
0
answers
829
views
Symmetric sparse direct solvers in scipy
scipy.linalg.solve, in its newer versions, has a parameter assume_a that can be used to specify that the matrix $A$ is symmetric ...
- 10.1k
4
votes
1
answer
392
views
Test matrices for large sparse overdetermined system of linear equations
I'm working on some c++ code to solve (conjugate gradient, least squares conjugate gradient, LSQR,..) large sparse overdetermined systems of linear equations. There is a twist to my matrices and the ...
- 143
4
votes
1
answer
3k
views
Iteratively solving 3D Poisson equation in MATLAB
I have written a function that sets up a sparse matrix A and RHS b for the 3D Poisson equation in a relatively efficient way. The set-up is nothing fancy: I have extended the 2D 5-point stencil to an ...
- 143
4
votes
2
answers
3k
views
Reordering sparse matrices in computational science
On page 3 of this document, there are some matrix forms for sparse matrices. I wonder if there are other forms used in computational problems encountered in physics, chemistry, etc., so that ...
- 273
4
votes
2
answers
640
views
Poisson-Nernst-Planck equations with ill-conditioned sparse matrix
I am trying to solve Poisson-Nernst-Planck system of equations for ions diffusion problem using finite volume method. Nernst-Planck equation for mass transport and Poisson equation for electrostatic ...
- 41
4
votes
1
answer
304
views
Choosing preconditioner for unsymmetric pressure-velocity coupled system
I'm working with pressure-velocity coupled systems. It means that instead of solving 4 different linear systems in segregated approach (1 for pressure and 3 for Ux, Uy, Uz), we can solve only one ...
- 41
3
votes
2
answers
437
views
Knapsack problem with fixed number of elements?
I am looking at an optimization problem that looks like this:
$$
\text{minimize}\;\; \mathbf{x}^TQ\mathbf x \;\;, \; \mathbf x \in \mathbb R^n, x_i \in \lbrace 0, 1 \rbrace\\
\text{subject to}\;\; ||...
- 189
3
votes
2
answers
569
views
Why iterative method: AMG preconditioned PCG is slower than Matlab direct method 'A\b'?
Recently, I have met a question that
a saying goes that for large linear system: iterative methods are required because of memory problem of direct methods.
But when I implement some experiments ...
- 961
3
votes
2
answers
1k
views
Dirichlet boundary condition for sparse matrix - Solving Ax=b only for free nodes?
I am solving Biot equation with sparse matrix in MATLAB. I have no problem with global sparse matrices assembly, but when I assign Dirichlet boundary condition, it is so slow.
From this topic, How to ...
- 33
1
vote
1
answer
523
views
Linear solve using CHLOMOD in C
I am using the open-source CHLOMOD (as here http://faculty.cse.tamu.edu/davis/suitesparse.html) in order to solve a linear system Ax=b (performing A/b=x) in my domain decomposition code but I am ...
- 37
1
vote
1
answer
3k
views
Ways to solve $Ax=b$ for a sparse (banded) $A$ with updates
I want to solve the time-dependent Schrodinger Equation using the Crank-Nicolson scheme. I end up with the following matrix equation
...
- 217
1
vote
1
answer
64
views
Is there an upper bound for fill-ins for indefinite triangular factorization?
For $A=LU$, or $A=LDL^T$ factorization, bandwidth is preserved when there is no pivoting. This is true even for indefinite A, see question. However, when there is pivoting band structure is destroyed, ...
- 245