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

37 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
280 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 ...
5
votes
0answers
133 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 ...
5
votes
0answers
492 views

Sparse matrix format and sparse-matrix sparse-matrix multiplication

I'm having some performance problems with my code dealing with the multiplication of big sparse matrices (stiffness and aerodynamic influence coefficient matrices). Mainly I have to multiply such ...
4
votes
0answers
80 views

How to construct a eigensolver targeting a specific type of matrix

I need to diagonalize such kind of matrix during research: it's n-by-n, with it's upper-left (n-1)-by-(n-1) corner be diagonal while the nth row & column are dense. It's observed that the self ...
4
votes
0answers
351 views

Optimisation of matrix exponential

I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 ...
4
votes
0answers
156 views

Preconditioning technique for large sparse non-hermitian matrix

I am attempting to solve a computational acoustics problem that involves solving an underlying sparse matrix. The size of the problem varies with grid size (3D) and fill-in's obviously make direct ...
4
votes
0answers
219 views

Adaptive mesh data structure for Fast Marching Method to overcome RAM limit

On an uniform mesh of positions in space $\ (x_i,y_j,z_k)$: $$\ x_i = x_0 + i\Delta x,\quad i=0,\ldots,n_x$$ $$\ y_j = y_0 + j\Delta y,\quad j=0,\ldots,n_y$$ $$\ z_k = z_0 + k\Delta z,\quad k=0,\...
3
votes
0answers
65 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
0answers
85 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 ...
3
votes
0answers
304 views

Efficient assembly of finite element matrix(coupled equations case)

I noticed this post, where spalloc and sparse are recommended for efficient assembly in Matlab. I personally use sparse ...
2
votes
0answers
84 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
117 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$ ...
2
votes
0answers
226 views

How to reuse permutation-orderings within scipy's SuperLU-wrapper?

i'm solving sparse linear equations within scipy 0.18 which internally resorts to SuperLU (after umfpack got removed due to license-issues). Current, i'm doing a complete re-factorization in each ...
2
votes
0answers
65 views

Fortran solver for the Sparse LSE problem

I was wondering if there is a Fortran library that contains a solver for the Sparse LSE(linear equality-constrained least squares) problem $$ min_{x}\|Cx-d\|^2 \text{ subject to } Ax=b $$ where $A$ ...
2
votes
0answers
142 views

Solvers for stiff initial value ODEs with sparse Jacobian

What ODE solvers are optimized for solving stiff systems with sparse Jacobian? Such systems appear, for instance, when a parabolic PDE is discretized in space using typical finite difference or finite ...
2
votes
0answers
897 views

How to solve singular non symmetric poisson equation with Neumann boundary condtions?

I am trying to solve 2D Poisson equations with Neumann boundary conditions. When the mesh is uniform, Poisson equation is singular and symmetric, so the method listed in Null Space Projection for ...
2
votes
0answers
99 views

Preconditioner for large size hermitian eigenvalue problems

Basically I try to compute several smallest eigenvalues of some sparse 50k*50k eigenvalue problems using matlab. $$Ax = \lambda Bx$$ With matlab eigs, it's not as fast as I expected. So I tried some ...
1
vote
0answers
49 views

Numerical methods. MDF (ILU) implementation

I am trying to implement Minimum Discarded Fill (MDF) Ordering algorithm for incomplete matrix factorization. The algorithm description is here on page 60 Preconditioning Techniques for a Newton–...
1
vote
1answer
105 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
79 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{...
1
vote
0answers
46 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
34 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 ...
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 ...
1
vote
0answers
415 views

Pseudoinverse of a large sparse matrix in r

This question was moved from Cross-Validated: https://stats.stackexchange.com/questions/274042/pseudoinverse-of-large-sparse-matrix-in-r I am trying to calculate the pseudoinverse of a large sparse ...
1
vote
0answers
59 views

Reduce large sparse linear operators to memory efficient loops?

I'm dealing a lot with large sparse linear operators these days and I'm quite new to them. A lot of the matrices I deal with originate with only a few unique integers, however, there are lots of them. ...
1
vote
0answers
212 views

How to reshape matrix into row-major order for MKL DSS?

I would like to use MKL to solve a sparse linear system. I chose the DSS (Direct Sparse Solver) interface, which implements the following steps: ...
1
vote
0answers
191 views

All eigenpairs of large sparse symmetric matrix

In advance I am sorry for my noobish question. I am a physics PHD student and basically I use python for my math/physics problems. But now I have a problem which requires more computing capacity and ...
1
vote
0answers
124 views

Updating factorization of Laplacian (add/remove edges)

For a graph $G=(V,E)$, recall that the unweighted Laplacian is $L:=D^\top D$, where $D\in\{-1,0,1\}^{|E|\times|V|}$ is the graph "gradient" operator that subtracts adjacent vertex values onto edges. ...
1
vote
0answers
558 views

Implementation of a direct solver in Fortran 90?

My question may be elementary, but it is quite essential as I am getting confused. Here I am supposed to solve the following equation: $Ax=B$ From my understanding I have options of using either ...
1
vote
0answers
260 views

Sparse Linear Algebra vs Dense Linear Algebra

I am interested in a reference in the literature that discusses the performance of Dense Linear Algebra (blas routines) and dense linear algebra (sparse blas routines). I am interested in knowing for ...
1
vote
0answers
91 views

Sparse matrix factorization of a rank deficient matrix by decomposition into linearly independent components

I've got a little conjecture I need to prove for a theoretical result related to causal Bayes net search with latent variables under sparsity constraints. If you're interested in the application ...
1
vote
0answers
236 views

Markowitz Pivoting to reduce size of a dense integer system

I am dealing with a large sparse integer matrix that I need to find the nullspace of. I've seen Markowitz Pivoting come up in several places discussing similar problems such as here: http://www....
0
votes
0answers
39 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 ...
0
votes
0answers
35 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 ...
0
votes
1answer
91 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} + ...
0
votes
0answers
402 views

how to pick a submatrix of a sparse matrix quickly(matlab)

I have a large sparse matrix A and i want to pick the submatrix of it to do block jacobi iterations. For the blocks, i have get a matrix Q that contains the index of nonzero entries in its Jth column ...
0
votes
0answers
193 views

Givens method for sparse matrix

I have a (very) large sparse matrix in CSC form and I'm supposed to factorize it. I've read that between Givens and Householder transformations, Givens is better for a sparse matrix. The problem is ...