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
2
votes
2answers
107 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 ...
4
votes
1answer
114 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
195 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
68 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
57 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
93 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
127 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
266 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
91 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
61 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
65 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
43 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
175 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
39 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
59 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: ...
0
votes
1answer
32 views

How to fill matrix entries for two-dimensional implicit finite-difference for the general case

If I have derived a finite-difference formula for a 2D problem, for example something like: $af_{i,j}+bf_{i-1,j}+cf_{i,j-1}+df_{i-1,j-1}=g_{i,j}$ where f is the unknown function on a grid and ...
2
votes
1answer
50 views

Best way to convert a sparse (containing zeros) covariance matrix into a correlation matrix?

I have a $100$x$100$ covariance matrix that looks like this. Some rows/cols are all-zero because those corresponding elements are not present in the sample from which covariance is calculated. I'm ...
3
votes
0answers
98 views

What is the algorithm to convert an adjacency matrix to a block diagonal structure?

I'm a little at loss as to what my supervisor meant by the "hierarchical block decomposition" of a matrix, but the goal is to put a sparse symmetric adjacency matrix into a block diagonal structure to ...
2
votes
0answers
42 views

How to determine the finite difference coefficient matrix in 2D with periodic BC?

I'm solving a PDE in matlab using ode15s, and since the spatial dimension is 2, and number of variables grow large very quickly, I need to supply the structure of ...
2
votes
1answer
179 views

Sparse Matrix Matrix multiplication using Intel MKL

Let $D$ be a sparse matrix. I want to compute $D\times D^T$. As $D$ is fairly large, so I am row-slicing $D$. That means for a range $(i,j)$, I am computing $C = D(i:j,:) \times D^T$ and performing ...
2
votes
0answers
97 views

What is the state-of-the-art in parallel sparse matrix and dense vector multiplication?

For sure, there has been many highly optimized library on this. But I am working on a matrix-free context since the problem size does not allow explicit storage of sparse matrix elements. I'd love ...
2
votes
1answer
120 views

Sparse matrix-matrix multiplication using AVX2

I have two sparse general matrices stored in CSR format I need to multiply. Is there any chance to gain performance using AVX2? In general the matrices are big (hundreds of millions of non-zeros and ...
2
votes
0answers
17 views

Barrier algorithm Gurobi and interior-point quadprog; what kind of matrices can it handle the best (sparse or dense, large or small problems)?

I am trying to solve a QP problem. Does anybody know the differences between the interior-point-convex algorithm of quadprog and the barrier method of Gurobi in terms which kind of matrices can the ...
-1
votes
1answer
42 views

Matrix requirements for cusparse*csrgemm2

I would like to perform a matrix multiplication like: $C=A*B*A'$ using cusparse library function cusparseDcsrgemm2. To do this I split it into two matrix-matrix multiplications where all matrices ...
0
votes
2answers
80 views

CSC Sparse Matrices: Why sort row data for Ax=b problems?

I have a matrix in Coordinate format and I will convert it to CSC. As a reference, the format I am using looks like this, but I am not using the pointerE matrix, which I think is superfluous. My ...
1
vote
2answers
92 views

How to understand the storage of the Hessenberg matrix of Krylov subspace matrix?

For the Krylov subspace method to solve the large sparse linear system, we first need to generate a subspace Km = span{v,Av,...A^{m-1}v}, which indeed a process ...
2
votes
2answers
277 views

Inverting really big symmetric block diagonal matrix

I have a really big symmetric 7.000.000 X 7.000.000 matrix that i would like to invert. The matrix is extremely sparse and it can be rearranged as to become a block diagonal matrix. The biggest blocks ...
1
vote
0answers
55 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
0answers
26 views

Multibody Systems modeling disadvantages [closed]

Multibody Systems modeling is a very systematic approach usually results in large sparse Jacbian matrix. I am working to model a system consisting of 11 bodies and 63 constraint equations as soon as i ...
5
votes
2answers
163 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
43 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
103 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
91 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
175 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
0answers
94 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
52 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
197 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
204 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
139 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
59 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
36 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
1answer
183 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
276 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
98 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
58 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
106 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
44 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
350 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
74 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
66 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(\...

1
2 3 4 5 6