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
-1
votes
0answers
55 views

When do we choose full orthogonalization method (FOM)? [duplicate]

Today, I have studied Full Orthogonalization Method (FOM), one of the Krylov subspace methods, using Y. Saad. Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia, PA, second edition, 2003. ...
4
votes
1answer
77 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 ...
0
votes
0answers
32 views

Fast algorithm for computing lower mode shapes and natural frequencies in MATLAB using sparse stiffness and mass matrices

I am looking for a fast algorithm for computing eigenvalues and eigenvectors from sparse stiffness and mass matrices in MATLAB. The eig(K, M) doesn't work with ...
1
vote
2answers
73 views

When should I write a matrix-vector function to handle the sparse matrix vector multiplication?

This semster, I have been studying the iterative methods for large sparse matrix system. But I have some questions. For large sparse matrix, we must use an economic storage to store them. The most ...
2
votes
1answer
53 views

What method to solve a sparse complex symmetric (non-Hermitian) system?

I have a sparse system (about 78% of zero entries) that is complex and symmetric (but not Hermitian). The following figure shows the structure of the problem. The off-diagonal blocks are incidence ...
2
votes
3answers
107 views

Is there any other sparse matrix data in matlab built-in file?

I want to do some numerical examples solving large sparse linear system Ax=b. And I want to use some data from Maltab itself because this experiments are easily ...
1
vote
1answer
70 views

(FEM) Efficient CRS vectors evaluation using elements connectivities

What is an efficient way of evaluating the column (col_ind) and the row (row_ptr) vectors for the CRS (Compressed Row Storage) storage format using the Connectivity Array? The Connectivity Array is a ...
1
vote
0answers
74 views

understanding Domain Decomposition with example

I am new in Domain Decomposition method. I am started to solve $-\Delta u = f$ in $\Omega$ and $u = 0$ on $\partial\Omega$. From that I get in $\Omega _1$ $$\begin{bmatrix}4&-1\\-1&4\end{...
0
votes
0answers
28 views

Why does the matlab command **chol(A)** slower than **chol(A,'lower')** for a large sparse SPD matrix?

For a SPD matrix A, there exists Cholesky factorization $A=LL^T$ or $A=R^TR$, where L, R are a lower and upper triangular matrix, respectively. Also in matlab, there has a command R = chol(A) which ...
1
vote
1answer
67 views

How to compute all the eigenvalues of a large sparse matrix using matlab?

In matlab, there are 2 commands named "eig" for full matrices and "eigs" for sparse matrices to compute eigenvalues of a matrix. And eig(A) computes all the eigenvalues of a full matrix and eigs(A) ...
5
votes
0answers
31 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 ...
1
vote
1answer
51 views

What is the format of saving sparse matrix in MATLAB?

We know that for lagre sparse matrices, we can use compressed sparse row (CSR) or compressed sparse column (CSC) format to store the sparse matrices so that we can save CPU memory. And the coordinate ...
1
vote
0answers
40 views

Hybrid Ellpack-Itpack (ELL) + COO Sparse Matrix Representation decomposition threshold

Hybrid ELL-COO sparse matrix representation can be done as in the picture, I was looking intensively, however I couldn't find out what is the threshold of decomposing the original matrix into ELL part ...
1
vote
0answers
30 views

How to use matlab **fft** function or other fast methods to solve a convection-diffusion system quickly?

for a convection-diffusion equation with Dirichlet boundary conditions as follows: $$-u''+qu'=f$$ Using centered difference for $u''$ and $u'$, we get a linear system $$Ax=b$$where matrix $A$ is ...
0
votes
1answer
75 views

Robin Boundary Condition with Implicit Upwind - Finite Difference Method for 2D Convection-Diffusion Equation

I am trying to solve a problem with 2D Convection-Diffusion equation with U = Concentration ($mg/m^{2}$) using Implicit Upwind Finite Difference Method like this $$ \frac{\partial U}{\partial t} + ...
2
votes
2answers
158 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 ...
1
vote
1answer
59 views

Incomplete LU decomposition of sparse matrix

I have a sparse matrix stored in CSR format. For this matrix, I would like to get the incomplete LU decomposition. I tried to find algorithms which can utilize the CSR format but I could not find ...
1
vote
1answer
51 views

Software for parallel incomplete LU factorisation

I am looking for a software package to compute incomplete LU factorisations in parallel. Further considerations are: The package must allow for arbitrary level-of-fill or threshold-based truncation. ...
1
vote
1answer
86 views

Sparse matrix inversion

I have the impedance matrix $Y$, formulated from an electrical network by augmented nodal analysis. The matrix $Y$ is shown as an image to illustrate its feature visually, where all the white blocks ...
0
votes
1answer
42 views

Plotting ratings matrix

Hello fellows and folks. I have been looking to do this for 1 month and still cannot find the way to do it. Here’s what’s going on: I have a csv file called ratings.csv with the following ...
1
vote
1answer
246 views

(FEM) Nodes reordering for sparse matrix storing techniques

Is it necessary to reorder nodes (using Reverse Cuthill-Mckee algorithm, for example) if I am already using a CSR or CSC storing technique? Because since CSR/CSC stores only non-zero elements I guess ...
2
votes
1answer
58 views

Problem of multiplication of big (sparse) matrix with numpy (python)

I wanted to multiply two simple (big and sparse) matrix with numpy. And I saw that the calculation fails when matrices are too big. If i take $X$ a random vector (size $n$). With pandas, I ...
4
votes
1answer
58 views

Solver for generalized eigenvalue problem with multipoint constraints

We have the following generalized eigenvalue (set of) problem(s) $$[K_R(\kappa)]\{u_R\} = \omega^2[M_R(\kappa)]\{u_R\}\quad \forall \kappa \in [\kappa_0, \kappa_1]$$ with \begin{align} &K_R(\...
3
votes
0answers
64 views

Numerical analysis, pivoting and incomplete LU decomposition

When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is ...
3
votes
1answer
120 views

Minimize a function with sparse Hessian

The problem I am trying to solve involves minimising a function with respect to a large number (probably 10,000+) of parameters. I can cheaply compute both its Jacobian and its Hessian. The Hessian is ...
4
votes
1answer
1k 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$...
2
votes
2answers
188 views

C standard for computational science

Which C standard should be used for computational science code ? Should we keep compatibility with C89/90/ANSI or jump to C99 or C11 ? Context: Code will use third-party : BLAS, LAPACK, MKL, ...
2
votes
1answer
249 views

Memory and time requirements of the scipy sparse spsolve

I have a system of fairly large set of linear equations (approximately 30K equations). I am using scipy.sparse.spsolve to solve these equations. Initially, I tried ...
3
votes
0answers
83 views

Why the MIRACLE of Lanczos/CG-like?

Lanczos/Arnoldi/Rietz/CG-like algorithm share the same core strategy... In each, a little miracle appears, most of the Gram-Schmidt inner products are zeroes! In others words, new direction need only ...
1
vote
0answers
72 views

Fast calculation of $A^T B$

I need to compute a matrix-matrix product, $A^T B$, where $A$ is $n \times r$ sparse, and $B$ is $n \times q$ dense. The number of rows $n$ is far larger than both $r$ and $q$. In fact $n$ is so large ...
7
votes
2answers
189 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
3answers
782 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 ...
4
votes
2answers
217 views

Moore-Penrose pseudoinverse of singular rank degenerate matrix

I am trying to attain the Moore-Penrose pseudoinverse of a very large, very sparse, rank-degenerate, singular, and square matrix. ($75000 \times 75000$, near rank). The matrix is a graph Laplacian and ...
2
votes
1answer
240 views

Which SciPy nonlinear solver when Jacobian is analytically known and sparse?

I have a nonlinear function fun with n inputs and n outputs. I also have a function jac which calculates the Jacobian, which is ...
4
votes
1answer
72 views

Method to Efficiently Solve “Centered” Least Squares without centering “A”

Suppose I want to solve $$\text{arg min}_x \frac{1}{2}\|\tilde{A}x - b\|_2^2 + \frac{1}{2}\|x - c\|_2^2$$ where $A$ is a wide sparse matrix and $\tilde{A} = A C_n = A (I - \mathbf{1}\, \mathbf{1}^T/...
1
vote
1answer
491 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 ...
6
votes
2answers
251 views

inertia count sparse matrix with dense low-rank perturbation

I would like to determine the number of negative eigenvalues (inertia count) of the $(N \times N)$ symmetric real matrix $K - \sigma M$, with $K$ a positive-definite sparse matrix and $M$ a positive-...
4
votes
1answer
110 views

Level scheduling of triangular sparse matrices

Assume one has a triangular sparse matrix and want to solve $Lx=b$ where $b$ and $L$ are known. This can be done easily by using forward substitution when $L$ is a lower triangular matrix. Forward ...
3
votes
1answer
130 views

How can a CG solver solve a non positive definite sparse matrix

I am using the CUSP CG solver and I ran it on couple of sparse matrices from the University of Florida sparse matrix collection. The solver was able to solve non positive definite sparse matrices. My ...
6
votes
1answer
160 views

Solving linear system of the form $ABx=b$

I would like to solve a linear system of the form $ABx=b$ in parallel, where $A$ and $B$ are large, sparse matrices. Currently, I am forming the system matrix $AB$ explicitly, but I would like to ...
4
votes
2answers
199 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 ...
2
votes
1answer
55 views

FFT of “implicitly” uniform data

I am trying to take a Fourier transform of a density field estimated from mock galaxy survey catalogs. Basically, you start with a list of galaxy positions, then you bin these positions over some ...
7
votes
2answers
594 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 ...
1
vote
1answer
105 views

Reordering algorithm for minimization of ram usage of a skyline matrix

The stiffness matrix of $Ax=B$ system of linear equations, where $A$ is an $n\times n$ symmetric matrix stored in the form of symmetric skyline matrix, that is associated with a finite element model ...
2
votes
1answer
40 views

Partial diagonalisation of large symmetric positive-definite band-diagonal matrices

I want to partially diagonalise real sparse symmetric positive-definite matrices, that are of dimension $n = 10^5$ and I need on the order of $k = 500$ of the smallest eigenvalues and eigenvectors. ...
8
votes
1answer
177 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 ...
2
votes
0answers
83 views

Acceleration of matrix geometric series

Suppose we want to find $x$ such that: $$x=b+Ax$$ where $A$ is a large sparse square matrix with eigenvalues in the unit circle. There are two representations of the solution: 1) $$x=(I-A)^{-1}b,$$...
2
votes
0answers
107 views

Left eigenvectors using ARPACK

I'm trying to find both the dominant $k$ left and right eigenvectors, that is, $$V_L\mathcal{A} = \Lambda V_L\\ \mathcal{A}V_R = V_R\Lambda\\ V_LV_R = I_{k\times k}$$ $V_L$ being the $k\times N$ ...
5
votes
1answer
120 views

Can redundant variables be beneficial for root-finding convergence

Suppose I have $n$ generally nonlinear equations for $n$ variables, like e.g. for $n=2$ the system $F(x,y)=0$ $$ \begin{aligned} x^2+2y-4&=0\\ \sqrt{8}x+y^2-5&=0 \end{aligned} $$ By ...
2
votes
2answers
785 views

Which python library for GPU sparse linear system solver library

I have a fluid dynamic solver written in python which I want to accelerate by moving the most expensive computations to the GPU. Ideally all arrays and sparse matrices used in my code should remain on ...