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.

1
vote
0answers
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. ...
2
votes
1answer
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 ...
1
vote
0answers
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: ...
4
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
4
votes
0answers
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 ...
1
vote
2answers
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'...
1
vote
2answers
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 ...
1
vote
2answers
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, ...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
11
votes
2answers
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 ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
7
votes
1answer
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-...
2
votes
1answer
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$ ...
1
vote
0answers
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. ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
5
votes
0answers
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 ...
4
votes
1answer
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$...
5
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
2answers
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. ...
1
vote
0answers
131 views

Solving system of equations with zeros on diagonal [closed]

I am using finite elements, Newton Raphson technique and MUMPS direct solver, to solve for $P$ in this equation: $$\frac{\delta K}{\delta x} \frac{\delta P}{\delta x}= \frac{\delta K B}{\delta x} + A$...
1
vote
0answers
463 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 ...
2
votes
2answers
509 views

Solve $AX=B$ where $A$ is a skyline matrix

Solve a matrix equation of the type $AX=B$, where $A$ is an $n \times n$ symmetric matrix stored in the form of symmetric skyline matrix. With the solution given by Bill and some more research on ...
7
votes
3answers
1k views

How to compute the rank of a large sparse matrix in MATLAB

I am interested in computing the ranks of fairly large, the largest being of magnitude $10^6$ x $10^6$, sparse matrices whose entires are all 0, 1, or -1. I have been trying to use Matlab to ...
1
vote
1answer
237 views

How efficient (compared to “normal” methods) is using a sparse finite difference matrix to solve differential equations?

Any differential operator can be written as a finite difference matrix acting on a vector of values. I recently used it to solve $\Delta A = j$ by writing the Laplacian as a finite difference ...
4
votes
1answer
2k views

Eigen - store sparse matrix as binary

I need to store large sparse matrices in Eigen. I cannot find anything in the library except the function below, in Eigen/Unsupported. The problem with saveMarket is, that it saves in text format. Due ...
2
votes
1answer
129 views

Topics about the deal.II finite element library class “SparsityPattern”

When learning the deal.II FE library, I am a bit confused about the mechanism of its "SparsityPattern" class. Through reading the documentation, I only got to know that it uses the Compressed Row ...
3
votes
1answer
114 views

Suggestions for an out-of-core sparse solver

I have a sparse $2\times10^5$ by $2\times10^5$ matrix with $3.2\times10^9$ non-zero elements. I want a sparse solver with out-of-core functionality. I have attempted to use Intel's ...
5
votes
1answer
103 views

Large scale triangular least squares

I have to solve the following least squares problem: \begin{equation} \| \left[ \begin{smallmatrix} \mathbf{L} \\ \mathbf{I} \end{smallmatrix} \right]\mathbf{x} - \mathbf{b} \|_2^2 \end{equation} ...
0
votes
1answer
113 views

solver linear system equation

I need to solve to solve a "large" symmetric sparse linear systems, with matrix size 8000? I heard about HSL, ITPACK, but I don't know how to use them, and I am working in C language.
6
votes
2answers
3k views

Calculating the log-determinant of a large sparse matrix

I need to calculate $\log(\det (\mathbf M_i))$ where the $\mathbf M_i$'s are large sparse matrices, which are real, symmetric and positive semi-definite. I hope to have between $10$ and $100$ of ...
1
vote
1answer
436 views

On the fly/matrix free SVD of large sparse matrix

I am trying to apply SVD to large sparse matrices. I already compared the performances of Propack and irlba to those of the matlab svd and ...
8
votes
2answers
3k views

How to efficiently implement Dirichlet boundary conditions in global sparse finite element stiffnes matrices

I am wondering how Dirichlet boundary conditions in global sparse finite element matrices are actually implemented efficiently. For example lets say that our global finite element matrix was: $$K = \...
3
votes
1answer
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 ...
1
vote
3answers
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
0answers
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$ ...
1
vote
1answer
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 ...
2
votes
2answers
229 views

High computational time in using backslash for soving sparse matrix

I built a sparse matrix A at each step as follows: % 1 < DX < 120000 A = sparse(i,j,s,DX,DX,6*DX) b = (1, DX) The ...
0
votes
1answer
87 views

Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

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}$ ...