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
3 votes
0 answers
86 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
2 votes
0 answers
90 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
  • 934
7 votes
3 answers
1k views

How large is large for direct solvers?

Let us say I want to solve a large sparse linear system. It is said that iterative solvers should be better than direct solvers in this case. But how large is large? What is the exact threshold beyond ...
timur's user avatar
  • 181
1 vote
1 answer
68 views

Fill-reducing ordering for computing the matrix product $A^T A$?

I have found many libraries for reducing filling when dong Cholesky factorisation on sparse matrices. However, I want to do fill-reduction for a different reason - given a $m\times n$ matrix $A,$ I ...
Ma Joad's user avatar
  • 161
0 votes
1 answer
64 views

Eigenvalue problem and pseudoinverse of a product of sparse matrices

If I have some dense matrix that can be decomposed into a product of sparse matrices with known(but different) sparsity patterns. Can I somehow use this information to more efficiently compute its ...
HRI's user avatar
  • 113
0 votes
0 answers
30 views

using scipy.sparse.linalg.eigsh for degenerate states in Bose Hubbard model

I am currently writing a code for the Bose-Hubbard model, and I am calculating the ground states and single-particle density matrix for different values of U and J. As U=0, one would see how the ...
Lorenzo Carfora's user avatar
2 votes
1 answer
397 views

How to leverage the GPU for parallel 3-body problem computations

I have a 3-body simulation which must run millions of times. As far as I know, the GPU shines when it gets to preform simple operations on huge matrices/arrays. Currently I'm debugging and running my ...
Remeraze's user avatar
2 votes
1 answer
59 views

Solving $(I-Q)x={\bf 1}$ for sub-stochastic sparse $Q$ of dimension 5M $\times$ 5M

I have a (right) sub-stochastic CSC sparse matrix $Q$ of dimension 5 million, with 200 million nonzero entries, which is a nonzero percentage of 0.0008%, so it is indeed extremely sparse. It is not ...
Set's user avatar
  • 503
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,122
0 votes
1 answer
201 views

Problems on the algebraic theory of sparse matrices

I have finished testing basic large densely parallel matrix multiplication on 4 gpu's ,and have done work on TSLU and TSQR on cpu's based on mpi. I am going to continue working on the theory of ...
Haitao Xiao's user avatar
0 votes
0 answers
211 views

Right blocked linear equation solver on Dense Algebra and Sparse Algebra

I have implemented 1D mesh parallel QR decomposition and LU decomposition,I would like to ask if a linear equation Ax=b,b is a large matrix and I need to shard b or Shard A,b at the same time. Is ...
Haitao Xiao's user avatar
4 votes
1 answer
331 views

How to efficient solve $e^{-tA} x =b$, where A is a very sparse matrix

I am going to solve an equation containing an exponential matrix $e^{tA} x =b$, which can be obtained naturally through $x=e^{-tA} b$. A is a 1million $\times$ 1 million matrix with stores 7.15 ...
Owen Jun's user avatar
  • 141
1 vote
2 answers
157 views

Are there good block sparse matrix solver libraries?

There are some great libraries with linear solvers for sparse matrices - SuiteSparse is the obvious one. The methods work on sparse matrices with scalar entries. However, often in optimization ...
user664303's user avatar
2 votes
0 answers
60 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
2 answers
220 views

Solving Poisson's equation without a Dirichlet boundary condition

Some context of what I am trying to do: I am trying to implement a function that uses the heat method to calculate geodesic distances in a tetrahedral mesh, and I want to calculate the distances for ...
Jake1234's user avatar
  • 145
0 votes
0 answers
104 views

What is the difference between approximations of mixed derivative and how to implement it

currently I am solving 2D nonlinear second order differential equation containing mixed derivative. I started searching how to descretisize it and found two formulas for 4th order approximation. First ...
Andrew's user avatar
  • 31
6 votes
1 answer
280 views

Accelerating the computation of scipy.sparse.linalg.expm_multiply

I have a tridiagonal antiHermitian matrix ($-i*Hami*t$) with nonzero elements only along the upper diagonal and lower diagonal, and the goal is to know the action of exponential of such matrix on a ...
code437's user avatar
  • 63
0 votes
1 answer
194 views

How to efficiently fill in, in parallel, a PETSc matrix from a COO sparse matrix?

Considering the following COO sparse matrix format, with repeated indices: ...
Riobaldo Tatarana's user avatar
1 vote
1 answer
213 views

Crank Nicolson Method with closed boundary conditions

I want to simulate 1D diffusion with a constant diffusion coefficient using the Crank-Nicolson method. $$\frac{\partial u (x,t)}{\partial t} = D \frac{\partial^2 u(x,t)}{\partial x^2}.$$ I take an ...
Jbag1212's user avatar
  • 111
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
2 votes
1 answer
115 views

How to numerically solve differential equations involving sines, cosines and inverses of the unknown function?

I'm very new to finite difference method and I am just introduced to methods of solving differential equation using finite difference method via sparse matrix method. I find that the main idea is to ...
Hari Sam's user avatar
1 vote
0 answers
180 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
2 votes
0 answers
98 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
0 votes
1 answer
183 views

Assign and print the results of CHOLMOD package

I am trying to solve a simple working example, a linear system $Ax=b$, where $A$ is sparse SPD and $b$ is dense, using CHOLMOD. ...
Riobaldo Tatarana's user avatar
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
3 votes
2 answers
264 views

Recover sparse matrix from linear operator

For many linear operators, it is easy to express them as a function. For example, to blur an image, simply compute a weighted sum of neighboring pixels (or even easier, import ...
John Doe's user avatar
0 votes
1 answer
206 views

How to speed up sparse matrix index operation in Matlab?

I need to create spare matrices with variable elements. Unfortunately, sparse matrix index operations are very slow. Is there any way to speed up the process? Maybe there are some tricks that I don't ...
Kim's user avatar
  • 21
1 vote
1 answer
86 views

Consider only triangular part of symmetric matrix for operations

It seems common practice to store only the upper or lower triangular part of a sparse symmetric matrix to save memory. Now I am wondering how, e.g. the SpMV kernel in CSR format is designed and how ...
vydesaster'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
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
1 vote
1 answer
138 views

Efficiency of developing PDE solvers using sparse matrices versus loops

I am new to solving PDEs, but have been looking at different implementations of finite difference and finite volume schemes. One thing I have noticed in different implementations is that some ...
krishnab's user avatar
  • 297
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,122
2 votes
0 answers
93 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
216 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
1 vote
1 answer
141 views

Sparse direct solver that works inside opened omp parellel region?

Does anyone know a library that implements sparse direct solver working in already open omp parallel region? The only library that I know that works with this requirement is Pardiso7.2 worth ~8K USD ...
Cesar Conopoima's user avatar
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
4 votes
2 answers
229 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 ...
nonagon's user avatar
  • 41
0 votes
2 answers
146 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 ...
Robert's user avatar
  • 3
4 votes
1 answer
112 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 ...
Jas Ter's user avatar
  • 149
3 votes
1 answer
544 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 ...
user196574's user avatar
1 vote
1 answer
988 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 ...
user avatar
1 vote
1 answer
174 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, ...
zhanghaoyuan's user avatar
2 votes
1 answer
1k 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 ...
anonuser01's user avatar
2 votes
1 answer
174 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 ...
bobo's user avatar
  • 91
6 votes
1 answer
259 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 ...
user3814483's user avatar
0 votes
1 answer
197 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 ...
SPARSE's user avatar
  • 169
1 vote
1 answer
802 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 ...
Solarflare0's user avatar
3 votes
0 answers
153 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
1 vote
0 answers
57 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
2 3 4 5
7