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

1
vote
0answers
39 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 ...
4
votes
2answers
93 views

Condition number from incomplete Cholesky factorization

I'm having difficulties patching together from what I read about obtaining the condition number of a real, symmetric, positive definite sparse matrix. In my code, I found that there is incomplete ...
0
votes
2answers
71 views

Parallel solver for sparse matrices on unstructured grids

I am trying to solve Euler equations on unstructured grids. Consequently, the problem reduces to solving Ax=b where A is a ...
0
votes
0answers
26 views

Does cyclic reduction require a square mesh for 2D FEM/FDM?

In a 2-dimensional finite difference method or finite element method (triangular elements, each node is connected to 6 neighbors), each node has a matrix entry to its horizontal and vertical ...
0
votes
1answer
79 views

Fastest linear solver for sparse positive semidefinite, striclty diagonally dominant matrix

What is the state of the art for fastest linear solver for sparse, positive semi definite and strictly diagonally dominant matrix with N varies from ~700 to ~3000, and about a 1/16 of the matrix is ...
2
votes
2answers
122 views

Solving Lx = b for big sparse Laplacian matrices

What algorithm is more practically suited in terms of performance for solving the $\mathbf{Lx=b}$ equation, where $\mathbf{L}$ is a generic Laplacian matrix (associated to a strongly connected graph, ...
0
votes
0answers
12 views

Finding correlations between sparse data with different temporal bases

The problem was one that came up during a standards committee meeting. If have one channel of data sampled every 100ms to record fault codes on a system (say an gasoline engine). It records value ...
4
votes
0answers
92 views

Sparse matrix ordering in Python

I would like to implement custom, domain-specific algorithms for sparse matrix orderings. I am looking for Python packages for ordering sparse matrices. It would be nice to have: The underlying ...
0
votes
1answer
90 views

solving underdetermined system of equations with a sparse matrix as input

I am using Matlab to solve Ax=b and my A is very large, sparse, binary and also rectangular. I saw the Matlab backlash \ operator help and it states that if A is rectangular then it will use the QR ...
15
votes
5answers
527 views

20% performance penalty for a nice software design

I'm writing a small library for sparse matrix computations as a way to teach myself to make the best use of object-oriented programming. I've worked really hard on having a nice object model, where ...
2
votes
3answers
249 views

Eigenvalues of a sparse banded nonsymmetric matrix from an elliptic operator

I have a sparse matrix coming from the discretization of a 3D elliptic PDE. The matrix is banded with seven non-zeros diagonals. The sparsity pattern of the matrix looks like this (the actual matrix ...
4
votes
1answer
100 views

Supernodal vs. Multifrontal Matrix Decompositions

Reading through Tim Davis' book Direct Methods For Sparse Linear Systems, he says that matlab can use a supernodal Cholesky decomposition but never uses a multifrontal Cholesky decomposition. At least ...
0
votes
1answer
82 views

Solver for large non-linear system of equations

I am curently using R package nleqslv for solving a non-linear system of equations with 300 variables. I need to scale this to the system with ~50k variables and naturally this does not scale very ...
0
votes
1answer
56 views

GMRES: Making the matrix square without solving for boundaries

How do we define the matrix for GMRES, if we do not want to solve the boundary elements but only the interior ones. I am using pentagonal elements so in a row there are 6 elements (cell itself + 5 ...
3
votes
3answers
137 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} ...
2
votes
3answers
196 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
145 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 ...
2
votes
2answers
241 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
148 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
96 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
132 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
141 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
125 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
41 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
37 views

an over view of sparsity promoting inversion techniques [closed]

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
243 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
149 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
21 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
149 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
27 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
31 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
176 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
211 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
140 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
149 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
143 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
87 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
22 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
134 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
145 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 ...
3
votes
1answer
210 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 ...
5
votes
1answer
449 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
91 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
243 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
177 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
66 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
138 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
152 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
400 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 ...
4
votes
4answers
458 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 ...