Skip to main content

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

67 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
0 answers
137 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 ...
xiaohuamao's user avatar
7 votes
0 answers
921 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 ...
murph_sof's user avatar
7 votes
0 answers
342 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 ...
vainia's user avatar
  • 121
5 votes
0 answers
45 views

Lowest eigenvalues of a matrix with divergent entries

In high energy physics we oftentimes encounter the following problem. For a given parametrized matrix $\{H_{ij}(\Lambda)\}$, we know that in the limit $\Lambda\to\infty$ some of its entries become ...
mavzolej's user avatar
  • 151
5 votes
0 answers
1k 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 ...
Federico Poloni's user avatar
5 votes
0 answers
89 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 ...
Izzy Vang's user avatar
5 votes
0 answers
540 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 ...
ferros's user avatar
  • 51
5 votes
0 answers
251 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 ...
Ambidextrous Anaconda's user avatar
5 votes
0 answers
241 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,\...
Andy's user avatar
  • 183
3 votes
0 answers
87 views

Eliminate variables from a large system of equations

I have a large system of equations $Ax=0$. For context, the equations are invariants of some model. $A$ is sparse and typically has more columns than rows ($m < n$). The $x$ vector can be divided ...
io6nZ's user avatar
  • 31
3 votes
0 answers
135 views

Fast Fourier Transform on Meshes

I have a (closed, manifold, oriented) triangular mesh for which I build a matrix $L\in\mathbb{R}^{n\times n}$ discretising the negated Laplace-Beltrami operator. The matrix $L$ is symmetric positive ...
lightxbulb's user avatar
  • 2,197
3 votes
0 answers
159 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 ...
Vy Trieu's user avatar
3 votes
0 answers
101 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 ...
nicholaswogan's user avatar
3 votes
0 answers
155 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 ...
Laplacian's user avatar
  • 171
3 votes
0 answers
860 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 ...
Charlie S's user avatar
  • 661
3 votes
0 answers
596 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 ...
rtviii's user avatar
  • 151
3 votes
0 answers
88 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 ...
Mathias's user avatar
  • 31
3 votes
0 answers
118 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 ...
sharl's user avatar
  • 57
3 votes
0 answers
137 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,$$...
cfp's user avatar
  • 131
3 votes
0 answers
389 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$ ...
Nikko's user avatar
  • 31
3 votes
0 answers
401 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 ...
sascha's user avatar
  • 131
3 votes
0 answers
347 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 ...
lorniper's user avatar
  • 593
2 votes
0 answers
95 views

Iterative solvers for problems in solid and structural mechanics

I am looking for comprehensive literature (papers, books, reports etc..) on iterative solvers for solid and structural mechanics problems to understand the best iterative solvers and preconditioners ...
Chenna K's user avatar
  • 944
2 votes
0 answers
70 views

Diagonalization of large sparse matrix, computational programme recommendation and methods

According to this link, All eigenpairs of large sparse symmetric matrix. The guy @Baranas seems to have given a very confident answer about solving the whole Eigen spectrum. May I know if anyone has ...
Lee Zhi Yan's user avatar
2 votes
0 answers
100 views

Parameter choice rules for L1 regularization?

I am solving an L1 regularized least squares of the form like: $$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \...
yourds's user avatar
  • 121
2 votes
0 answers
101 views

How to save multiplication computation time between a dense vector and a not that sparse matrix?

I am trying to compute $\mathbf{X}\mathbf{u}$ for many times in my algorithm, where $\mathbf{X}\in \mathbb{R}^{n\times m}$ and $\mathbf{u} \in \mathbb{R}^{m}$. The problem is that, during the ...
Xun Maoapo's user avatar
2 votes
0 answers
67 views

Sparse generalized symmetric eigensystem solver

Can anyone recommend a good software for solving generalized symmetric eigenvalue problems of the form, $$ A x = \lambda B x $$ where $A,B$ are symmetric and sparse, and $B$ is positive definite? I ...
vibe's user avatar
  • 1,058
2 votes
0 answers
57 views

Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R?

Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R to the end of the diagonal? As an example, consider the following snippet of MATLAB ...
wyer33's user avatar
  • 767
2 votes
0 answers
44 views

Iterative methods for underestimate of smallest eigenvalue for large sparse matrices

I recently read the paper "EUCLIDEAN-NORM ERROR BOUNDS FOR SYMMLQ AND CG" by Estrin et al. and there they use an underestimate (i.e. something in $(0,\lambda_{min}]$) of the smallest ...
lightxbulb's user avatar
  • 2,197
2 votes
0 answers
98 views

How to find eigvals/eigvecs of huge symmetric tridiagonal matrix using multiple processes or threads?

In python, there is a function in scipy (scipy.linalg.eigh_tridiagonal) which is extremely efficient for an exact diagonalization of a symmetric tridiagonal matrix (...
Stelladuck's user avatar
2 votes
0 answers
231 views

solve Ax=b for outrigger A matrix python

I implement Crank-Nicolson 2D finite-difference method. I get a matrix A which is banded with 1 band above and below the main diagonal, but also contains 2 additional bands , further apart from the ...
velenos14's user avatar
  • 131
2 votes
0 answers
119 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)?
user38651's user avatar
2 votes
0 answers
126 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 ...
Physicist's user avatar
  • 217
2 votes
0 answers
127 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 ...
Izzy Vang's user avatar
2 votes
0 answers
86 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$ ...
Patrick's user avatar
  • 21
2 votes
0 answers
355 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 ...
fred's user avatar
  • 1,000
2 votes
0 answers
156 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 ...
jokersobak's user avatar
2 votes
0 answers
1k 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 ...
Simon's user avatar
  • 21
2 votes
0 answers
112 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 ...
lorniper's user avatar
  • 593
1 vote
0 answers
54 views

Assembling a sparse matrix for the PaStiX solver

I've been searching the whole afternoon for some documentation or code sample showing how to assemble a sparse matrix of a problem to be solved with PaStiX, but couldn't find any. The relevant module ...
cesss's user avatar
  • 131
1 vote
0 answers
194 views

Solving 2D Poisson equation with mixed boundary conditions in Python

I am trying to numerically solve the Poisson's equation $$ u_{xx} + u_{yy} = - \cos(x) \quad \text{if} - \pi/2 \leq x \leq \pi/2 \quad \text{0 otherwise} $$ The domain is the rectangle with vertices ...
user82261's user avatar
  • 119
1 vote
0 answers
60 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 ...
Laplacian's user avatar
  • 171
1 vote
0 answers
68 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(...
Pedro Secchi's user avatar
1 vote
0 answers
114 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 ...
Resa's user avatar
  • 29
1 vote
0 answers
69 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 ...
gTcV's user avatar
  • 445
1 vote
0 answers
214 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 ...
user2348209's user avatar
1 vote
0 answers
79 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–...
Anya's user avatar
  • 21
1 vote
0 answers
135 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{...
420's user avatar
  • 41
1 vote
0 answers
209 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 ...
mmain's user avatar
  • 113
1 vote
0 answers
78 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 ...
Happy's user avatar
  • 971