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
2answers
50 views

Calculating the log-determinant of a large sparse matrix

I need to calculate $\log(\det (\mathbf M_i))$ where the $\mathbf M_i$'s are large sparse matrices, which are real, symmetric and positive semi-definite. I hope to have between $10$ and $100$ of ...
1
vote
1answer
39 views

On the flight/matrix free SVD of large sparse matrix

I am trying to apply SVD to large sparse matrices. I already compared the performances of Propack and irlba to those of the matlab svd and svds. These two packages enhance significantly the computing ...
2
votes
2answers
77 views

How to efficiently implement Dirichlet boundary conditions in global sparse finite element stiffnes matrices

I am wondering how Dirichlet boundary conditions in global sparse finite element matrices are actually implemented efficiently. For example lets say that our global finite element matrix was: $$K = ...
3
votes
1answer
56 views

Sparse Matrix Reordering

Matrix reorderings are important for many direct solvers. Sometimes the objective is to reduce the bandwith or the generated fill in by LU Decomposition. I am interested in a reordering which reduces ...
1
vote
3answers
66 views

Constructing sparsity pattern of the Jacobian of a FORTRAN subroutine

I need to calculate the Jacobian matrix of a subroutine F(U). Both F and U are of size N(=O($10^5$)). Using Tapenade, I differentiated the routine in tangent mode. I cannot calculate the full Jacobian ...
4
votes
1answer
72 views

Choosing preconditioner for unsymmetric pressure-velocity coupled system

I'm working with pressure-velocity coupled systems. It means that instead of solving 4 different linear systems in segregated approach (1 for pressure and 3 for Ux, Uy, Uz), we can solve only one ...
1
vote
0answers
39 views

How to convert MPIAIJ to SEQAIJ matrix in petsc/petsc4py?

I am curious, if there is a function to convert MPIAIJ (distributed matrices in AIJ format) to a SEQAIJ matrix that lie on a single processor. It is possible to do such an operation for PETSc vectors ...
2
votes
0answers
32 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$ ...
1
vote
0answers
45 views

solve linear system of equation of a large sparse symetric positive definite matrix

I want to invert large matrices ($10^4x10^4$ to $10^6x10^6$) but sparce (less than 100 non-zero entries per line) on clusters with 16 to 48 processors per node. I'm looking for an efficient method to ...
2
votes
2answers
121 views

High computational time in using backslash for soving sparse matrix

I built a sparse matrix A at each step as follows: % 1 < DX < 120000 A = sparse(i,j,s,DX,DX,6*DX) b = (1, DX) The ...
0
votes
1answer
40 views

Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...
1
vote
0answers
79 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 ...
2
votes
1answer
49 views

Sparse matrix vector product using PETSC

I am trying to do a simple parallel sparse matrix vector multiplications using PETSC. My sparse matrix is a simple tridiagonal laplacian matrix, which is distributed over multiple processors using ...
1
vote
2answers
120 views

How to use the basic Sparse matrix operations (multiplication, .etc) in PyCUDA

I try to use sparse matrix operations in GPU in Python and now try to use PyCUDA with theano. But I can't find how to do sparse matrix and vector multiplication. I only got an example showing how to ...
1
vote
1answer
50 views

Why does `symrcm` create larger band width?

When I run the following (in Matlab) on a sparse matrix $A$, I get larger band width. The symrcm (symmetric reverse Cuthill-McKee permutation) is not guarenteed to ...
2
votes
1answer
123 views

Solve Ax=B where B is a matrix in parallell

I try to solve the problem $Ax=B$ where $A$ is a large sparse $n\times n$ matrix, and $B$ is a dense $n\times m$ matrix (here $n=754850$ and $m=182$). The backslash operator yields correct solution ...
2
votes
1answer
85 views

Sparse iterative out-of-core parallel solver

Is there an iterative sparse parallel solver with out of core capabilities? I need to solve a very large system of equations. I have implemented direct sparse parallel solvers in core and out of core ...
1
vote
1answer
60 views

Sparse linear system of certain type

Let $n_1,n_2 \in \mathbb{N}$ and $n=n_1n_2$ and $b\in \mathbb{R}^n$. I have a SPD-matrix $A=(a_{i,j})\in \mathbb{R}^{n \times n}$ with $a_{i,j}=0$ if $|i-j| \notin \{0,1,n_1\}$. Can we solve the ...
0
votes
1answer
63 views

Iterative algorithms for sparsity using a function for operator A in Ax=b

I am going to solve an linear iterative inverse problem. I have two functions in matlab which one of them play the forward and ...
6
votes
2answers
211 views

calculating eigenvector components of a given vector

I have some vector $V$ which can be decomposed into the eigenspace of the hermitian sparse operator $M$: $V = \sum_i v_i \hat{m}_i$ Is there a way to find the $\hat{m}_i$ (the eigenvector itself) ...
1
vote
1answer
74 views

What is the cost of factorization for one-dimensional sparse problems?

In Golub and Van Loan's book, Matrix Computations, page 606, it is stated that: With standard discretizations, 2-dimensional problems can be solved with $O(n^{3/2})$ work and $O(n \log{n})$ ...
0
votes
0answers
152 views

Phase retrieval via SDP (semidefinite program) of 2D test image (Matrix completion)

In SDP based phase retrieval we have intensity measurement (abs(FFT2(x))^2) of the form A(xo) = |ak,x|^2 =b^2, phase retrieval is then find x that obeys A(xo)=b The quadratic measurements can be ...
1
vote
1answer
49 views

Is there an upper bound for fill-ins for indefinite triangular factorization?

For $A=LU$, or $A=LDL^T$ factorization, bandwidth is preserved when there is no pivoting. This is true even for indefinite A, see question. However, when there is pivoting band structure is destroyed, ...
1
vote
2answers
87 views

Time complexity for sparse direct solver for SPD system with respect to number of equations, bandwidth, number of nonzeros?

I am looking for information on the time complexity for solving sparse system Ax=b with direct solver. This system results from a finite-element discretization of an elliptic problem. The matrix A ...
4
votes
2answers
68 views

Is the bandwidth of indefinite A equal to its factor L in LDL^T?

In George, Liu, and Ng's book Computer Solutions of Sparse Linear Systems, it has been shown that bandwidth of $A$ is equal to bandwidth of its factors in $LL^T$.(section 4.3) However, I guess this is ...
0
votes
0answers
124 views

how to pick a submatrix of a sparse matrix quickly(matlab)

I have a large sparse matrix A and i want to pick the submatrix of it to do block jacobi iterations. For the blocks, i have get a matrix Q that contains the index of nonzero entries in its Jth column ...
2
votes
0answers
74 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
185 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 ...
1
vote
3answers
172 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
36 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
128 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 ...
4
votes
2answers
304 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, ...
5
votes
1answer
204 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
132 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
556 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
325 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
187 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
144 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
88 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
338 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
205 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
359 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 ...
5
votes
4answers
583 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 ...
1
vote
1answer
368 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
172 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
247 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
296 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
140 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
46 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
40 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 ...