Problems in which an operator or function can be represented with asymptotically less data than the naive representation. Not limited to sparse matrices.
0
votes
1answer
33 views
Solver for sparse linearly-constrained non-linear least-squares [closed]
Reposted from stackoverflow:
Are there any algorithms or solvers for solving non-linear least-squares problems where the jacobian is known to always be sparse, and the solution is constrained with ...
0
votes
1answer
81 views
Issues with solving large sparse linear equations
I have some issues solving sparse linear equations Ax = b
My matrix A is sparse with dimension of 5 million by 5 million. Actually, it is a combination of two matrices. One is tridiagonal and the ...
5
votes
2answers
187 views
Solving a sparse and highly ill-conditioned system
I intend to solve Ax = b where A is complex, sparse, unsymmetric and highly ill-conditioned (condition number ~ 1E+20) square or rectangular matrix. I have been able to solve the system with ZGELSS in ...
0
votes
0answers
60 views
Recommendation for any good books or articles which cover sparse coding?
I've watched a few Jeff Hawkins's lectures on youtube and read his book but would like to know more. Any suggestions?
4
votes
1answer
82 views
Sparse matrix implementation of the Kalman Filter?
I have a Kalman Filter based modelling code that I have developed for a near-real time regional ionospheric mapping application. The code assimilates data from different sensors into a map (described ...
8
votes
1answer
107 views
Why does SciPy eigsh() produce erroneous eigenvalues in case of harmonic oscillator?
I'm developing some larger code to perform eigenvalue computations of huge sparse matrices, in the context of computational physics. I test my routines against the simple harmonic oscillator in one ...
4
votes
1answer
120 views
Are there any specialized methods available for solving structurally symmetric sparse linear systems?
When solving $Ax=b$, prior knowledge about $A$'s structure can help in designing an efficient solver which exploits this information (e.g conjugate gradient method is to be used when $A$ is ...
5
votes
3answers
136 views
computing the determinant of a dense nonsymmetric 100x100 matrix having very big and very small eigenvalues
The motivation for my question is the following: in one of Project Euler questions there is a need to count the spanning trees of a rectangular grid graph of dimension 100x500. By the Matrix-Tree ...
3
votes
2answers
151 views
How to solve block tridiagonal matrix using Thomas algorithm
Thomas algorithm can be used to solve a tridiagonal matrix:
$$
\begin{bmatrix}
{b_ 1} & {c_ 1} & { } & { } & { 0 } \\
{a_ 2} & {b_ 2} & {c_ 2} & { } & { ...
3
votes
2answers
64 views
Reordering sparse matrices in computational science
On page 3 of this document, there are some matrix forms for sparse matrices. I wonder if there are other forms used in computational problems encountered in physics, chemistry, etc., so that ...
1
vote
2answers
93 views
What sparse solver supports diagonal storage format
I'm writing finite-difference method program using C. The stiffness matrix is symmetrical and band. For its storage I'd like to use Sparse Diagonal Storage format.
Could someone tell please, what ...
6
votes
4answers
146 views
Best choice of solver for a large sparse symmetric (but not positive definite) system
I am presently working on solving very large symmetric (but not positive definite) systems, generated by some certain algorithms. These matrices have a nice block sparsity which can be used for ...
5
votes
3answers
179 views
Take advantage of the sparsity of b in AX=b
There is a lot of info about how to use the sparsity pattern of A in order to solve $Ax = b$. However I can't find much about using the sparsity pattern of b. Let me take a concrete example:
Let us ...
2
votes
0answers
53 views
Adaptive mesh data structure for Fast Marching Method to overcome RAM limit
On an uniform mesh of positions in space $\ (xi,yj,zk)$:
$\ xi = x0 + i*dx, 0 <=i<nx$
$\ yj = y0 + j*dy, 0 <=j<ny$
$\ zk = z0 + k*dz, 0 <=k<nz$
I have a velocity function: ...
5
votes
1answer
112 views
preconditioner for a matrix-free method to solve Ax=b
I need to solve Ax=b, but I realize that even if it is sparse, storing the matrix coefficients of my problem will take too much memory.
So now I'm considering using a matrix-free method, because the ...
6
votes
3answers
168 views
Sparse linear solver for many right-hand sides
I need to solve the same sparse linear system (300x300 to 1000x1000) with many right hand sides (300 to 1000).
In addition to this first problem, I would also like to solve different systems, but with ...
2
votes
1answer
66 views
Algorithms for Compressed Sparse Rows
Is there a general survey on the basic algorithms for the compressed sparse rows format (like transposition, multiplication, addition, ...)? While it is not hard to write effective algorithms for ...
4
votes
3answers
355 views
Efficient assembly of finite element matrix in MATLAB
Question
What is the most efficient algorithm for finding a row of a matrix which matches a given row? This is the same as a table lookup based on multiple criteria.
Context
Finite Element Matrices ...
4
votes
2answers
104 views
Efficiency of Repeated Sparse Matrix-Vector Products
I recently read Wolfgang's answer to the question found here and found myself wondering about a related followup question.
Assume you have two sparse matrices $A$ and $B$. You need to do the ...
2
votes
1answer
102 views
What is the runtime complexity of MATLAB operation A*B where A and B are general sparse matrices?
I tried to search the answer and I found that method cs_multiply from this book has been adopted for the purpose of multiplication of two general sparse matrices in MATLAB.
In the book it says that
...
1
vote
1answer
206 views
Sparse Matrix Library for GPU
Anyone knows a good library which implements basic sparse matrix operations such as transpose, SpMV eigenvalues etc. in GPU (cuda/opencl) .
Thanks
1
vote
2answers
196 views
Implementing PageRank using the Power Method
I am trying to implement the PageRank algorithm described in this paper (Fig. 1). Here is the breakdown of the steps:
where:
pT is a probability distribution ...
4
votes
1answer
149 views
How to get sparse complex matrices from my code to PETSc efficiently
What is the most efficient way to get a complex sparse matrix from my Fortran code to PETSc? I understand that this is problem dependent, so I tried to give as many relevant details as possible below.
...
5
votes
1answer
102 views
Is there a way to inspect the graph of a sparse matrix with PETSc?
I am currently trying to code the CA-CG method within the PETSc framework. A mandatory step in this process is the implementation of the "matrix powers kernel" algorithm for a generic sparse matrix.
...
4
votes
3answers
403 views
Storing a large, sparse array for R and Python
I've been working in R but sometimes switching to python. I'd like a more inter-language portable way of storing a large array than a csv file. (The particular csv file I'm dealing with is about 10^6 ...
9
votes
5answers
281 views
What is the best way to determine the number of non zeros in sparse matrix multiplication?
I was wondering whether there is a fast and efficient method to find the number of non zeros in advance for sparse matrix multiplication operation assuming both matrices are in CSC or CSR format.
I ...
0
votes
1answer
95 views
Quickly computing inversion of a large sparse partial stochastic matrix
Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing ...
7
votes
1answer
130 views
Solving a system with a small rank diagonal update
Suppose I have the original large, sparse linear system: $A\textbf{x}_0=\textbf{b}_0$. Now, I do not have $A^{-1}$ as A is too large to factor or any sort of decomposition of $A$, but assume that I ...
4
votes
3answers
202 views
Solving shifted linear systems with LU factorization
I am interested in solving a sequence of shifted linear systems $(A+\sigma I)x = b$ for various values of $\sigma$. The matrix $A$ is sparse and not too large, so I have its LU factorization ...
7
votes
1answer
205 views
Does PETSc ever make use of LAPACK libraries for sparse matrix math?
Does compiling PETSc with an external BLAS/LAPACK library significantly affect performance on sparse matrices, or does it only use those libraries for dense matrix math?
5
votes
2answers
255 views
Taxonomy of ILU preconditioners
I learned that for BiCGStab solver for sparse linear systems it's pretty much always necessary to use a preconditioner. I realized by now that choosing a good one is problem dependent.
Surfing the ...
5
votes
2answers
159 views
Large-scale generalized eigenvalue problem with low rank LHS matrix
Assume that we have generalized eigenvalue problem:
$B^HB\textbf{x} = \lambda A\textbf{x}$
where $A$ is an nxn Hermitian sparse matrix (n is very large, so we do not have $A^{-1}$ but can solve ...
5
votes
3answers
197 views
Multiply Multiple Sparse Matrices
When we calculate products of multiple matrices, e.g., $ABC$, do you think it can be done in a cheaper way than as two consecutive multiplications? Note that I'm not talking about applying matrices to ...
12
votes
3answers
366 views
Solving $(G^TA^{-1}G)x = b$ without inverting $A$
I have matrices A and G. A is sparse and is nxn with n very large (can be on the order of several million.) G is an nxm tall matrix with m rather small (1 < m < 1000) and each column can only ...
7
votes
2answers
163 views
What is the overhead in sparse matrix multiplication
Does matrix multiplication (both Mat*Mat, and Mat*Vec) scale with number of non-zeros, or with the size of the matrix? Or some combination of the two.
What about with shape.
For example, I have a ...
3
votes
2answers
197 views
Solving sparse matrix systems which can be reordered to block diagonal form
I have a class of matrices $A$ which are created by a domain decomposition method. Each matrix represents several subproblems of equal size, and I know that for some permutation matrix $P$,
$PAP^T$ ...
4
votes
2answers
638 views
How to parallelize the computation of eigenvalues of a sparse symmetric matrix in MATLAB?
I have a similarity matrix which is symmetric and sparse. How can I parallelize the computation of the eigenvalues of this matrix in MATLAB?
5
votes
4answers
377 views
What are the best Python packages/interfaces to sparse direct solvers?
Please list the Python package (petsc4py, etc...) and the sparse direct solvers it supports. One (community-wiki) answer per package, please.
5
votes
2answers
146 views
Is it possible to ignore/discard part of a matrix when finding eigenvalues?
I have have multiple large matrices for which I need to find the largest absolute eigenvalue. I know that there is a large submatrix that does not vary. Is it possible to ignore/discard the submatrix?
...
5
votes
1answer
226 views
How does a Sparse Direct Solver know about dimensionality of a problem being solved?
It is claimed that the time and memory complexities of sparse direct solver are $O(N^2)$ and $O(N^{4/3})$ for 3D problems and $O(N^{1.5})$ and $O(N \log N)$ for 2D, respectively.
But how does a ...
12
votes
5answers
2k views
What is the fastest way to calculate the largest eigenvalue of a general matrix?
EDIT: I am testing if any eigenvalues have a magnitude of one or greater.
I need to find the largest absolute eigenvalue of a large sparse, non-symmetric matrix.
I have been using R's eigen() ...
7
votes
3answers
168 views
Computing the characteristic polynomial of real sparse matrix
Given a generic sparse matrix $A \in \mathbb{R}^{n\times n}$ with m << n (correction: $m \ll n^2$) non-zero elements (typically $m \in {\cal O}(n)$). $A$ is generic in the sense that it has no ...
6
votes
1answer
211 views
Sparse hermitian eigensystems: are there better techniques than Arpack or TRLan?
As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
7
votes
3answers
485 views
Solving a non-symmetric non-diagonally dominant sparse system the best way
I faintly recall from my early "numerics" lectures that iterative linear solvers for $Ax=b$ often require that when $A$ is decomposed as
$$A=D + M$$
where D is a diagonal matrix and $M$ has zero ...
