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

212 questions
56 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. ...
323 views

### Fastest way to solve a sparse unsymmetric system many times

I have to solve a system $Ax^{(n)} = b^{(n)}$ many times, $A$ being a sparse (pentadiagonal in most part of its structure), unsymmetric, constant matrix. Currently, I am performing the LU ...
178 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: ...
309 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 ...
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 ...
86 views

### Iterative single variable solutions in large linear systems

I have a system where $A$ is a large $n\times n$ marix with fast MVMs. It may have many nonzero entries (albeit in a structured way so as to allow fast MVMs), and is not necessarily diagonally ...
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 ...
165 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 ...
159 views

### How to complete sparse matrix?

I am trying to solve an equation by a meshfree method. Shape functions (and their derivatives) have a compact support domain. So, over a given integration cell used for numerical integration, only a ...
135 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 ...
120 views

### How is the dense system usually dealt with in spectral method?

Unlike finite element (FEM) or finite difference methods (FDM), where the original PDE is transformed into a sparse linear system, spectral methods return a dense linear system. For a large system, it'...
465 views

### Find a permutation matrix (using the Matlab's function $symrcm$) of a matrix $A(2:end, 2:end)$

I've the following Matlab code: r = symrcm(A(2:end, 2:end)); prcm = [1 r + 1]; spy(A(prcm, prcm)); where A should be sparse ...
55 views

### BLAS3 in Multifrontal Sparse Decomposition

I wonder how one manages to use BLAS level 3 operations in the multifrontal sparse decomposition algorithm. As far as I understand, the algorithm proceeds as follows: For each row/column pair, ...
631 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 ...
378 views

### Use of scipy sparse in ode solver

I am trying to solve a differential equation system $$x´=Ax\quad \text{with } x(0) = f(x)$$ in Python, where $A$ indeed is a complex sparse matrix. For now i have been solving the system using the ...
1k views

### Compute all eigenvalues of a very big and very sparse adjacency matrix

I have two graphs with nearly n~100000 nodes each. In both graphs, each node is connected to exactly 3 other nodes so the adjacency matrix is symmetric and very sparse. The hard part is I need all ...
386 views

### Fast C++ implementation of sparse binary matrices

I am looking for the subject. The size of matrices will be around 1000x2000 elements with linear amount of ones (say, 6000 ones in the whole matrix). The operations I will use the most: iterating ...
202 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 ...
378 views

### Efficient algorithm for solving linear system with symmetric near-tridiagonal matrix?

I would like to solve the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$, with $$\mathbf{A}=\mathbf{T}+\mathbf{C}$$ where $\mathbf{T}$ is a symmetric tridiagonal matrix and $\mathbf{C}$ is a corner-...
1k views

### Applying the result of Cuthill-McKee in SciPy

I have applied SciPy's implementation of the Cuthill-McKee algorithm to a $48 \times 48$ sparse non-symmetric matrix in Compressed Sparse Row (CSR) format and the output is an array of length $48$ ...
116 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. ...
113 views

### CHOLMOD implementation

I am working on a domain decomposition code in C that uses CHOLMOD to approximate grid values for a PDE in each sub-domain. The issue I have is that the methods use Matrix Market format, which is not ...
85 views

### Multiplication of random sparse matrices

I am given 2 unstructured (i.e. do not posses any special sparsity pattern like banded/triangular/etc.) sparse matrices $A$ and $B$ of dimension ($n$ x $n$) and density $d$ each (thus each matrix ...
212 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 ...
414 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 ...
131 views

### Solve for $C$ such that $C^{T}AC$ is banded of given width

Given a symmetric matrix $A$, the Lanczos algorithm outputs $C$ such that $C^{T}AC$ is tridiagonal. Is there a generalization of this such that $C^{T}AC$ is banded of specific width $w$? Note that $C$...
270 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 ...
191 views

### Probability of reconstructing a word using c substrings from a random sample

Consider a voice recording split into it's phonemes as our sample $S=(s_1,...,s_k) \in \Omega = P^k$. The number of phonemes is $|P| = 40$. Then I have a word $w = (w_1,...,w_n) \in P^n$. I want to ...
609 views

### Sparse Matrix Matrix multiplication terminology (SpGEMM or SpMM?)

I have seen sparse matrix-matrix multiplication commonly referred to as SpGEMM, which means general/generalised sparse matrix-matrix multiplication. I've seen it once or twice (forgot where) as SpMM. ...
131 views

102 views

### Sparse Matrix Reordering

Matrix reorderings are important for many direct solvers. Sometimes the objective is to reduce the bandwith or the generated fill in by LU Decomposition. I am interested in a reordering which reduces ...
428 views

### Constructing sparsity pattern of the Jacobian of a FORTRAN subroutine

I need to calculate the Jacobian matrix of a subroutine F(U). Both F and U are of size N(=O($10^5$)). Using Tapenade, I differentiated the routine in tangent mode. I cannot calculate the full Jacobian ...
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 ...
408 views

### How to convert MPIAIJ to SEQAIJ matrix in petsc/petsc4py?

I am curious, if there is a function to convert MPIAIJ (distributed matrices in AIJ format) to a SEQAIJ matrix that lie on a single processor. It is possible to do such an operation for PETSc vectors ...
63 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$ ...
155 views

### solve linear system of equation of a large sparse symetric positive definite matrix

I want to invert large matrices ($10^4 \times 10^4$ to $10^6 \times 10^6$) but sparse (less than $100$ non-zero entries per line) on clusters with $16$ to $48$ processors per node. I'm looking for an ...
I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...