Problems in which an operator or function can be represented with asymptotically less data than the naive representation. Not limited to sparse matrices.

learn more… | top users | synonyms

3
votes
3answers
79 views

Efficient solver for a symmetric tridiagonal system where the upper/lower diagonals are offset

I'm looking for an efficient way to solve a symmetric tridiagonal system $Mx = d$, where the upper and lower diagonals of $M$ are offset from the main diagonal by $k$ rows/columns: $$ \begin{bmatrix} ...
1
vote
0answers
42 views

Dense distributed matrix

A dense matrix is distributed for parallel computation column-wise, then multiplied from left & right by sparse matrices. What would be appropriate c++ libraries for these tasks?
0
votes
0answers
64 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 ...
0
votes
0answers
14 views

Finding eigenvalues of a Hermitian matrix using “eigsh” function from scipy

I am trying to use the scipy.linalg.sparse.eigsh function of scipy to find eigevalues of a Hermitian matrix. In the link below it says that eigsh can handle Hermitian matrices but when I run it gives ...
2
votes
1answer
134 views

Good Finite Element Library for a small project

I'm currently working on this project and I have a basic structural analyzer that uses the finite element method. Essentially, I turn each block into a set of trusses, construct a stiffness matrix ...
0
votes
1answer
34 views

computing the inverse of a large block diagonal sparse matrix in r

I would like to compute the inverse of some large block diagonal sparse matrix. The number of rows and columns is somewhat over 50,000. The blocks are 12 by 12 and are sparse (27 non zero elements). ...
1
vote
0answers
54 views

Assembling sparse matrix in PETSC for Poisson equation

I am a novice at PETSC, and I have been trying to write an FVM code for steady heat conduction in 2D using PETSC (square, regular grid, Dirichlet boundaries) Since the large matrix , say A, will be ...
1
vote
2answers
80 views

What sparse linear programming solver it is better to use?

I have the following LP problem: $$ \min \limits_{\varepsilon, x_{1}, \ldots, x_{n}}f(\varepsilon, x_{1}, \ldots, x_{n}) = \varepsilon \;\;\;\;\; s.t. \;\;C x \geq 0, \;\; x_{i}^{0} - \varepsilon ...
1
vote
1answer
83 views

Sparse matrix - matrix multiplication

How can a sparse matrix - matrix product be calculated? I know the 'classic' / mathematical way of doing it, but it seems pretty inefficient. I thought about storing the first matrix in CSR form and ...
1
vote
0answers
122 views

Givens method for sparse matrix

I have a (very) large sparse matrix in CSC form and I'm supposed to factorize it. I've read that between Givens and Householder transformations, Givens is better for a sparse matrix. The problem is ...
1
vote
0answers
39 views

Sparse matrix factorization of a rank deficient matrix by decomposition into linearly independent components

I've got a little conjecture I need to prove for a theoretical result related to causal Bayes net search with latent variables under sparsity constraints. If you're interested in the application ...
1
vote
1answer
33 views

an over view of sparsity promoting inversion techniques

I have a function called f(x) which is convex and I can have access to its first order derivative , my objective function is $$\ J(\bf{x}) = f(\bf{x}) + \lambda |\bf{x}|_0 $$ $$\ \bigtriangledown ...
7
votes
2answers
197 views

Which novel data structures are used in adaptive FEM?

A lot of adaptive FEM libraries use more advanced mesh data structures to handle adding/removing nodes, edges, triangles, tetrahedra, etc. For example, the p4est library uses octree data structures ...
2
votes
2answers
81 views

Poisson-Nernst-Planck equations with ill-conditioned sparse matrix

I am trying to solve Poisson-Nernst-Planck system of equations for ions diffusion problem using finite volume method. Nernst-Planck equation for mass transport and Poisson equation for electrostatic ...
0
votes
0answers
17 views

Minimum sparsity of two randomly populated matrices leading to performance increase when switchting from dense to sparse matrix multiplication

Given two 2D matrices A, B which are going to be multiplied by a matrix multiplication algorithm. Properties of matrix A The columns are grouped into blocks of size N. Within each block identified ...
3
votes
2answers
105 views

Solving Newton-Raphson step with ill-conditioned sparse matrix

I am trying to build a complex simulator for the transport of mass & heat in porous media. I am currently following coarsely the algorithm laid out in an older software and have got the simulator ...
0
votes
0answers
21 views

Markowitz Pivoting to reduce size of a dense integer system

I am dealing with a large sparse integer matrix that I need to find the nullspace of. I've seen Markowitz Pivoting come up in several places discussing similar problems such as here: ...
0
votes
0answers
19 views

MLLL algorithm for sparse, integer bases to find a nullspace

I am trying to find a suitable algorithm that can find a basis for the nullspace of a sparse, integer matrix. Reading A Course in Computational Algebraic Number Theory by Cohen, an algorithm based ...
3
votes
2answers
158 views

Consumer GPUs for sparse matrices (e.g. FEA)

Are consumer grade GPUs (like the NVidia Geforce series) used for solving sparse linear equations systems in a professional setting? For example, by engineers performing finite element analysis? ...
4
votes
1answer
112 views

Nullspace algorithm for a sparse matrix

I am dealing with large, sparse, rational matrices that I need to determine the nullspace of. Currently, I have one that is about 12000x12000 (but not square), where one in every 2000ish elements is ...
5
votes
2answers
115 views

Inverting a pressure matrix for fluid simulation

I am implementing a fluid simulator as my numerical methods course project and I have to compute pressure at each simulation step. Basically, that means solving an equation $Ap = b$, where $A$ is a ...
2
votes
3answers
131 views

Sparse, underdetermined system of linear equations

I'm looking for an algorithm to solve the underdetermined system of linear equations $$\mathbf{A}\,\mathbf{x} = \mathbf{b}$$ with $\mathbf{A} \in \mathbb{R}^{n\times n}$, $\mathbf{b} \in ...
2
votes
2answers
95 views

Cropping in Sparse Matrix

Let $A$ be an $M \times N$ sparse matrix stored in compressed column format, in a C-like programming environment. I am interested in the best solution to get a sub-matrix of $A$. In MATLAB notation, ...
2
votes
1answer
83 views

Sparse matrices origins

I am using the sparse matrices provided by the University of Florida Sparse Matrix Collection and most matrices are accompanied with little description of the problem or discipline from which the ...
0
votes
0answers
19 views

Differences between methods for solving linear equation system [duplicate]

I have a huge linear equation system in this form: F=K.Δ as usual form of problems in the finite element method, where the F vector and K are known and Δ vector is unknown. There are several methods ...
3
votes
1answer
79 views

indirect method for least-squares with inequality constraints

I aim to find $x \in \mathbb{R}^n$ that $\min_x |D \cdot F \cdot x|^2$ subject to $x_i = X_i$ and $x_j \geq X_j$ , $i \in I, j \in J$ and I and J partition ${1\cdots N}$ into two sets. it is ...
2
votes
1answer
67 views

Generalized eigenvalue problem using ARPACK

Is it possible to solve the eigenvalue problem: $$Ax = \lambda Mx$$ using ARPACK when $A$ and $M$ are both non-symmetric complex matrices? According to this documentation, the function ...
2
votes
1answer
127 views

Sparse matrices that represent common stencil operations

I am not sure if this is the correct place to ask this question! Is there a data set such as the University of Florida Sparse Matrix Collection which is produced from stencil operations? Or is ...
4
votes
1answer
309 views

How to use Lanczos method to compute eigenvalues and eigenvectors

I have a sparse and symmetric matrix A(n x n). The method Lanczos tranforms matrix A into tridiagonal and symmetric matrix T and the Lanczos vectors in matrix V. From there how do I compute k ...
2
votes
1answer
82 views

Numerically efficient way to compute sparse-matrix arithmetic on GPU?

Can anyone tell me some very good/efficient numerial algorthims for GPU/CUDA to compute multiplication/ between sparse matrices (its good if you can recommend me some research papers)? I googled ...
8
votes
1answer
177 views

Why SVD is talk about less than QR and LU for sparse matrix?

For example the C++ sparse matrix libraries I used -- Eigen and SuiteSparse, they seem not to have any SVD funcitionality for sparse matrix. So just curious, is SVD more difficult than QR/LU for ...
4
votes
3answers
135 views

Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D ...
2
votes
0answers
59 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 ...
1
vote
1answer
107 views

PETSc: Blocking matrices using MatCreateSeqBAIJ and MatSetValuesBlocked

I am a little confused with PETSc's documentation for MatSetValuesBlocked. The code below works fine for matrices when I choose small block sizes, but I get errors ...
8
votes
4answers
133 views

Are there any quad-double arithmetic sparse matrix package?

I am working on some ill-conditioned large sparse linear system of equations. I want to use double-double arithmetic or quad-double arithmetic to solve them. I know that there is a package named MPACK ...
3
votes
1answer
312 views

How to calculate ALL of the eigenvalues/eigenvectors of a large, sparse, asymmetric matrix?

I am trying to calculate all of the eigenvectors/eigenvalues of large (40000x40000), sparse, asymmetric matrix. I am using MATLAB and have 3 GB of working memory. The way I am calculating them is by ...
3
votes
4answers
290 views

Library that performs sparse matrix-vector and matrix-transpose-vector multiplication

My main interest is sparse matrix-vector and matrix-transpose-vector multiplication of the form y=y+AA'x. Is there any library that performs ...
2
votes
3answers
252 views

What is the best solver for solving a large sparse indefinite system

What's the best solver that can solve a large sparse but indefinite matrix?
3
votes
2answers
157 views

Memory management for solving large sparse systems with UMFPACK

I'm using umfpack for solving large systems of equation. However, I'm constantly getting out of memory issues for even modest size problems as pre2, torso3, ohne2 Hamrle3 (all from Tim Devis's ...
4
votes
1answer
169 views

Sparse Incomplete Cholesky

I'm looking for an efficient, multicore, library to do incomplete cholesky (possibly modified). Many ILU code exists, but I can't find much about IC except in PETSC or Pastix. Could some of you drop ...
3
votes
1answer
687 views

Algorithm for Sparse-Matrix Inverse

I have a $50000\times 50000$ matrix $A$ sparse matrix containing only 5 non-zero elements in each row. Now the problem is that the diagonal elements and the constants (in $B$ matrix such that $AX=B$) ...
2
votes
2answers
217 views

Sources to get source codes for sparse matrix solvers (non-symmetric matrix)

For an implicit scheme I want to solve system $Ax=B$, where $A$ is a non-symmetric square matrix. I want source codes of large sparse matrix solvers (e.g. LU-SGS) to use in my code which is in C ...
5
votes
2answers
190 views

Computing smallest eigenvectors of a sparse matrix, having its inverse

I'm a bit confused by the vast amount of literature on solving eigenvalue problems. I have a sparse (large) matrix which I have already factored (by Cholesky or LDU). I would like to compute few ...
3
votes
1answer
60 views

Computing sparse matrix products into a dense result

I need to assemble a matrix (in dense form, of moderate size, say dimension 1000) which is most easily expressed as the product of several (4) sparse matrices. These matrices are most easily expressed ...
0
votes
1answer
129 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
3answers
829 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 ...
6
votes
4answers
319 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 ...
9
votes
1answer
383 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
149 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
323 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 ...