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
7
votes
0answers
89 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 ...
3
votes
2answers
112 views

nnz-preserving sparse matrix multiplication

Let A and B be sparse matrices in $ \mathbb{R}^{m\times m}$ with (roughly) the same density $p$. I want to efficiently compute a matrix $C$ that in some sense is "closest" to $AB$ while ...
0
votes
2answers
70 views

Where can I find matrices and it's preconditioner for testing?

I want to find some kinds of matrices for testing my code such as GMRES , MINRES and so on. But I can't find some testing matrices and corresponding preconditioner to verify my program. I know some ...
4
votes
1answer
98 views

Sparse least squares with a (black-box) ill-conditioned operator

It was suggested on math.stackexchange.com that I try to ask this question here. Consider a bounded linear operator $A : U \to V$ where $U$ is finite dimensional and where $V$ is a separable Hilbert ...
3
votes
1answer
315 views

A method for finding the number of eigenvectors with a given, known eigenvalue

Is there a method for finding the number of eigenvectors with a given eigenvalue? I do not need the eigenvectors themselves, and to find the eigenvectors seems quite tough, given the comments on the ...
1
vote
1answer
136 views

Givens rotation algorithm without matrix-matrix multiplication

I would like to implement a givenRotation algorithm without having matrix-matrix multiplication. Matrix-vector is fine or just for looping. I am to decompose a rectangular (m+1)xm Hessenberg matrix. I ...
1
vote
1answer
96 views

What is the difference between Adittive Schwarz as a preprocessor and a solver?

As we all know, the Additive Schwarz approach can be used as either solver or preconditioner, however, my question is, what is the difference between the two? In other words, how to use AS as solver, ...
1
vote
1answer
106 views

What is the conventional approach for sparse matrix multiplication?

When you're multiplying sparse matrices against other sparse matrices or dense matrices, what is the conventional approach for each? How are the sparse matrices stored? What does matrix multiplication ...
2
votes
1answer
91 views

Bounds for the optimal bandwidth of 2D/3D FEM stiffness matrices

is anyone here aware of whether there exist bounds on the optimal bandwidths of 2D/3D FEM stiffness matrices? Edit: more specifically, I would like to have bounds on the minimum bandwidth after ...
6
votes
1answer
193 views

Algorithm for solving systems which are nearly symmetric/adjoint?

I am familiar with Cholesky decomposition and LU factorization for solving systems of linear equations. I have a problem where I have large sparse matrices (say, 1000x1000 or larger) where only one or ...
0
votes
1answer
40 views

Best search algorithm for optimal weight factor in SOR method

I had written an algorithm that searches for the optimal weight parameter to be implemented in the successive-over relaxation (SOR) method which worked cleanly by vectorizing the interval and for ...
1
vote
1answer
122 views

Efficiency of scipy.sparse.linalg.expm_multiply with sparse vs unsparse vectors

From the package scipy.sparse.linalg in Python, calling expm_multiply(X, v) allows you to compute the vector ...
3
votes
0answers
111 views

Invert a huge sparse operator;

please help me with this question, I want to invert a huge sparse (non-circulant) this below in a $Ax=y$ equation: $$(\lambda I+ \beta D+ \sigma C)x=y$$ where I is an Identity Matrix,D is a Diagonal ...
1
vote
0answers
35 views

Tolerance is not satisfied in eigsh function

I am diagonalizing a sparse matrix of size $153600\times 153600$ via eigsh function. I did not set the tolerance to specific value, so it would be the default value ...
1
vote
0answers
50 views

Viable algorithms for efficiently solving a block matrix system with non-uniform sparsity structure

I am trying to use Newton's method to get a stationary solution for a system of equations of the following form: $$ \begin{Bmatrix} \frac{\partial x}{\partial t} \\ 0 \end{Bmatrix} = \begin{Bmatrix} f(...
3
votes
1answer
148 views

How can I extract the banded or block diagonal part of a sparse matrix in MATLAB?

Given a large sparse (square) matrix in MATLAB, how can I extract the banded or the block-diagonal parts (of fixed size) of it efficiently? These are useful operations when prototyping and testing ...
3
votes
0answers
77 views

Solving PDEs: What is the best way to deal with non-banded/dense jacobians?

I have a system of PDEs describing atmospheric chemistry and transport. I use finite-differences to make my system of PDEs into a system of ~10,000 ODEs. I then integrate the ODEs forward in time with ...
3
votes
1answer
100 views

`eigsh` (Lanczos algorithm) slows down for degenerate eigenvalues

I have a complex Hermitian matrix of size about $70000\times 70000$. I want about 100 eigenvalues near 0. However, I know that every eigenvalues are two-fold degenerate. I found out that the running ...
1
vote
1answer
88 views

RCM better than Nested dissection? (For FEM discretizations in 2D and 3D)

I realize this might be a too general question but here goes nothing: I am trying different re-ordering strategies and checking the fill-in of $A=LU$. I have 2D ($p=1$, $h=1/40$ on $\Omega = [-1,1]^2$)...
3
votes
0answers
68 views

Does shift-invert method has invertibility issue?

Please note that I have nearly zero background on numerical methods. I understand the shift invert method as described in SciPy Tutorial The main argument of the above link is as follows. Suppose we ...
2
votes
0answers
60 views

Software for solving large systems of linear equations over gf(2)

What available solvers are there for linear equation solver over GF(2) (Boolean), capable of dealing with large sparse systems (in the 10k - 100k variables range)?
0
votes
3answers
277 views

How to apply the boundary condition when global stiffness matrix is stored in csr format? [duplicate]

I am solving the poisson equation and I constructed the global stiffness matrix in compressed row storage format. Then I wrote the preconditioned conjugate gradient solver for solving the system of ...
1
vote
0answers
82 views

C.S.R method in finite element matrix assembly

I have solved the 2D Poisson equation using finite element method with simplex triangular element in MATLAB. First, I generated the triangular mesh using pdetool in ...
1
vote
0answers
52 views

Nonsymmetric permutations for LU factorisation of symmetric matrix

Let $A$ be a symmetric matrix. It is then well known that computing the LU factorisation of $PAP^T$ instead of $A$ for a suitably chosen permutation matrix $P$ can greatly reduce fill-in. My question ...
3
votes
1answer
119 views

Nonlinear root solving libraries which accept a Jacobian in band-storage

I'm in search for a library for solving large systems of non-linear equations, similar to MINPACK, but unlike MINPACK, can accept a Jacobian in band-storage. My Jacobian is sometimes not invertible, ...
1
vote
2answers
135 views

Solving a specific sparse linear system without dense materialization

I need to (computationally) solve a system of equations, for the purposes of an interior point method, of the form $$ \left[\begin{array}{cc}B & A^T \\ A & 0\end{array}\right] \left[\begin{...
12
votes
1answer
2k 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 ...
6
votes
1answer
276 views

Efficiently computing $e^{tX}$ for many different values of $t$

Given an anti-Hermitian and sparse matrix $X$, I am using Python (NumPy and SciPy) to compute the matrix exponential $f(t) := e^{tX}$ for many values of $t$. The method I am currently using is to ...
1
vote
1answer
123 views

Complexity of solving an image differential linear system

Define an "image differential linear system" as a linear system $A\mathbf{x}=\mathbf{b}$ wherein $\mathbf{x}$ contains the ($\mathbb{R}$) pixels of an image and each row of $A$ constrains ...
6
votes
1answer
370 views

Parallelize Scipy iterative methods for linear equation systems(bicgstab) in Python

I need to solve linear equations system Ax = b, where A is a sparse CSR matrix with size 500 000 x 500 000. I'am using scipy.bicgstab and it takes almost 10min to solve this system on my PC and I need ...
1
vote
0answers
101 views

performance comparison between PETSc and SLATE

We want to start a new project to solve a large-scale inverse problem (O(10^6) number of parameters) to invert for subsurface wave speeds. We will use FEM to solve forward and adjoint PDEs. In our ...
0
votes
0answers
93 views

How to make a directed graph symmetric?

Say I have a directed graph given as an adjacency matrix $A$ in CSR format represented by the arrays ia (row indexes) and ja (...
2
votes
1answer
36 views

In Eigen, can a sparse matrix contain vectors/objects instead of simple scalar values?

I need to have a sparse matrix whose elements are not simple numbers, but objects, e.g. a couple of floating point values and a bunch of integer indices. I am wondering if Eigen has something similar, ...
3
votes
1answer
129 views

Choice of iterative solver for a sparse asymmetric matrix with symmetric structure

I have a sparse $nxn$ matrix A with pretty interesting structure. It has a block structure with symmetric structure but asymmetric blocks. Expressed mathematically the block $A_{jk} = A_{kj}$ but $A_{...
2
votes
3answers
119 views

Create a sparse matrix

I am writing a FE program which calculates the displacements under a uniform load. I want to store the stiffness matrix in sparse form(COO) without using an external library.Assume an upper-bound for ...
2
votes
2answers
146 views

L1 least squares minimization with a sparse matrix

I have the following problem: $$\min_{x\in \mathbb{R}^n}\|Ax-b\|_1$$ where the matrix $A$ is large and sparse. I am looking for methods/code that can minimize this efficiently. References are very ...
6
votes
2answers
1k 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 ...
2
votes
3answers
511 views

On the reordering of sparse matrices

I have been reading on different techniques used to reorder sparse matrices to achieve better performance, the most popular being the Cuthill-McKee or Reverse Cuthill-McKee algorithm. Most of those ...
0
votes
0answers
78 views

Derivative-free ill-conditioned non-linear least squares

I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as ...
1
vote
1answer
247 views

Implementation of sparse matrix SVD for GPU

I have a sparse matrix $W$ which is almost-squared ($N+1 \times N$) and I would like to know the eigenvalues of $A = W^T W$. $A$ is Hermitian so the eigenvalues are real-positive valued. The usual ...
0
votes
1answer
195 views

Solving large sparse system

I am working on a problem with very large sparse matrices. I'd like to compute $A^{-1} B$, that is a crucial part of converting DAE to ODE (and there is no workaround). Here size of $A$ is 2E+5 x 2E+5 ...
1
vote
1answer
175 views

Efficient way to solve a set of linear equations $Ax=b$ when $A$ is sparse and some elements of $b$ are equal to zero

I have a set of linear equations, $Ax=b$. And about half of the elements in the right-hand side (vector $b$) are equal to zero. My system matrix $A$ is a sparse complex matrix. And $A$ is in the size ...
7
votes
2answers
349 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 "...
3
votes
0answers
284 views

Compute Nullspace of Sparse Matrix

I am computing the nullspace of a sparse rectangular $m$ x $n$ matrix $A$, where $m$ << $n$. I do this by computing the QR decomposition of $A^T$ and extract the $n-m$ right-most columns of the ...
0
votes
1answer
219 views

Solving a sparse linear system using transpose of lower triangular matrix without copying

I have a sparse lower-triangular matrix $L$, and a right-hand side $b$, and I'd like to solve the linear system $$L^T x = b$$ but without explicitly creating $L^T$. Ideally, I could write something ...
2
votes
1answer
146 views

Fast way to build stiffness directly as CSC matrix

I have been working on finite element code in Fortran 2008, and have implemented my own sparse matrix types. I have found that mapping local stiffness matrices (real type) to a global COO sparse type ...
0
votes
1answer
132 views

How to delete $n^{th}$ row and $n^{th}$ column of a matrix K in Petsc and restructure it?

I have a matrix K in Petsc. I want to delete the $n^{th}$ row and $n^{th}$ column of this matrix and restructure it. I am a beginner in Petsc. Can you suggest how to do it? Example: I have matrix K ...
3
votes
1answer
519 views

Why is 'scipy.sparse.linalg.spilu' less efficient than 'scipy.linalg.lu' for sparse matrix?

I have a matrix B which is sparse and try to utilize a function scipy.sparse.linalg.spilu specialized for sparse matrix to ...
2
votes
1answer
67 views

what does `cusparse<t>csrsv2_analysis()` do?

In cuSPARSE, you can solve a sparse triangular linear system by calling cusparse<t>csrsv2_solve(). However, you need to call ...
3
votes
1answer
345 views

Fast nonzero indices per row/column for (sparse) 2D numpy array

I am looking for the fastest way to obtain a list of the nonzero indices of a 2D array per row and per column. The following is a working piece of code: ...

1
2 3 4 5 6