Questions tagged [sparse]

Problems in which an operator or function can be represented with asymptotically less data than the naive representation. Not limited to sparse matrices.

49
votes
4answers
7k 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 (...
15
votes
4answers
1k 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 ...
27
votes
7answers
20k 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 ...
4
votes
4answers
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 ...
8
votes
2answers
253 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) ...
9
votes
2answers
491 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 ...
4
votes
1answer
218 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 ...
12
votes
3answers
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 ...
6
votes
2answers
1k 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, ...
8
votes
2answers
3k 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 = \...
6
votes
2answers
507 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 ...
4
votes
5answers
9k 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} & { } & { }...
3
votes
1answer
2k 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 ...
17
votes
5answers
6k 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 ...
7
votes
1answer
845 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 ...
4
votes
2answers
439 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 ...
3
votes
2answers
634 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 ...
9
votes
1answer
318 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 ...
6
votes
2answers
1k 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 ...
6
votes
2answers
238 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? ...
5
votes
1answer
847 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 ...
5
votes
1answer
86 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 ...
4
votes
2answers
162 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 ...
4
votes
1answer
2k views

How to calculate ALL of the eigenvalues/eigenvectors of a large, sparse, asymmetric matrix?

I am trying to calculate all of the eigenvectors/eigenvalues of large (40000x40000), sparse, asymmetric matrix. I am using MATLAB and have 3 GB of working memory. The way I am calculating them is by ...
4
votes
1answer
179 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 ...
1
vote
1answer
55 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, ...
0
votes
1answer
214 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 ...