Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [sparse]

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

2
votes
0answers
24 views

Solver for generalized eigenvalue problem with multipoint constraints

We have the following generalized eigenvalue (set of) problem(s) $$[K_R(\kappa)]\{u_R\} = \omega^2[M_R(\kappa)]\{u_R\}\quad \forall \kappa \in [\kappa_0, \kappa_1]$$ with \begin{align} &K_R(\...
0
votes
0answers
43 views

Reduced row echelon form of a rectangular sparse matrix

I am trying to find the reduced row echelon form of (m x n, m >= n or m <= n) a rectangular sparse matrix (CSR format) to possibly deal with millions rows and columns which causes memory allocation ...
2
votes
0answers
61 views

Numerical analysis, pivoting and incomplete LU decomposition

When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is ...
3
votes
1answer
71 views

Minimize a function with sparse Hessian

The problem I am trying to solve involves minimising a function with respect to a large number (probably 10,000+) of parameters. I can cheaply compute both its Jacobian and its Hessian. The Hessian is ...
2
votes
1answer
179 views

Which C++ linear algebra library is probably the fastest on solving huge sparse [square matrix] linear system?

I am developing a 2D CFD solver for fluid-particle interaction. To solve Navier-Stokes equations on a grid of size $10000\times 10000$ cells (or >1 million cells), a large linear system $Ax=b$ with $A$...
2
votes
2answers
175 views

C standard for computational science

Which C standard should be used for computational science code ? Should we keep compatibility with C89/90/ANSI or jump to C99 or C11 ? Context: Code will use third-party : BLAS, LAPACK, MKL, ...
1
vote
1answer
58 views

Memory and time requirements of the scipy sparse spsolve

I have a system of fairly large set of linear equations (approximately 30K equations). I am using scipy.sparse.spsolve to solve these equations. Initially, I tried ...
3
votes
0answers
79 views

Why the MIRACLE of Lanczos/CG-like?

Lanczos/Arnoldi/Rietz/CG-like algorithm share the same core strategy... In each, a little miracle appears, most of the Gram-Schmidt inner products are zeroes! In others words, new direction need only ...
1
vote
0answers
64 views

Fast calculation of $A^T B$

I need to compute a matrix-matrix product, $A^T B$, where $A$ is $n \times r$ sparse, and $B$ is $n \times q$ dense. The number of rows $n$ is far larger than both $r$ and $q$. In fact $n$ is so large ...
0
votes
0answers
58 views

Open source distributed sparse-matrix vector multiplication library

What is the current state-of-the-art open source library that has an efficient implementation distributed memory sparse matrix-vector multiplication? I need to perform repeated SpMVs and I am looking ...
7
votes
2answers
124 views

Integer operations vs floating point operations

I have been working with an algorithm, which uses additions of floating point vectors, (sparse matrix of floats)x(dense vector of floats) dot products I recently found out that I can get the same ...
8
votes
3answers
266 views

Rule of thumb for sparse vs dense matrix storage

Suppose I know the expected sparsity of a matrix (i.e. the number of non-zeros / total possible number of non-zeros). Is there a rule of thumb (perhaps approximate) for deciding whether to use sparse ...
3
votes
2answers
138 views

Moore-Penrose pseudoinverse of singular rank degenerate matrix

I am trying to attain the Moore-Penrose pseudoinverse of a very large, very sparse, rank-degenerate, singular, and square matrix. ($75000 \times 75000$, near rank). The matrix is a graph Laplacian and ...
2
votes
0answers
92 views

Which SciPy nonlinear solver when Jacobian is analytically known and sparse?

I have a nonlinear function fun with n inputs and n outputs. I also have a function jac which calculates the Jacobian, which is ...
4
votes
1answer
69 views

Method to Efficiently Solve “Centered” Least Squares without centering “A”

Suppose I want to solve $$\text{arg min}_x \frac{1}{2}\|\tilde{A}x - b\|_2^2 + \frac{1}{2}\|x - c\|_2^2$$ where $A$ is a wide sparse matrix and $\tilde{A} = A C_n = A (I - \mathbf{1}\, \mathbf{1}^T/...
1
vote
1answer
191 views

Ways to solve $Ax=b$ for a sparse (banded) $A$ with updates

I want to solve the time-dependent Schrodinger Equation using the Crank-Nicolson scheme. I end up with the following matrix equation ...
6
votes
2answers
240 views

inertia count sparse matrix with dense low-rank perturbation

I would like to determine the number of negative eigenvalues (inertia count) of the $(N \times N)$ symmetric real matrix $K - \sigma M$, with $K$ a positive-definite sparse matrix and $M$ a positive-...
4
votes
1answer
94 views

Level scheduling of triangular sparse matrices

Assume one has a triangular sparse matrix and want to solve $Lx=b$ where $b$ and $L$ are known. This can be done easily by using forward substitution when $L$ is a lower triangular matrix. Forward ...
2
votes
1answer
85 views

How can a CG solver solve a non positive definite sparse matrix

I am using the CUSP CG solver and I ran it on couple of sparse matrices from the University of Florida sparse matrix collection. The solver was able to solve non positive definite sparse matrices. My ...
6
votes
1answer
146 views

Solving linear system of the form $ABx=b$

I would like to solve a linear system of the form $ABx=b$ in parallel, where $A$ and $B$ are large, sparse matrices. Currently, I am forming the system matrix $AB$ explicitly, but I would like to ...
4
votes
2answers
143 views

How “sparse” should a sparse matrix be to see benefits?

I have a matrix, whose size scales as $2^N$ (assume even $N$). In each row of the matrix, only about $2^{N/2}$ of the entries are filled ($N$ can be somewhere between 10 and 40, depending on what's ...
2
votes
1answer
45 views

FFT of “implicitly” uniform data

I am trying to take a Fourier transform of a density field estimated from mock galaxy survey catalogs. Basically, you start with a list of galaxy positions, then you bin these positions over some ...
6
votes
2answers
520 views

Why does sparse linear algebra have a low arithmetic intensity?

I often see the terms "low arithmetic intensity" and "memory-bound" associated with sparse matrix operations. However, my intuition is that a sparse matrix operation should be less memory-bound, if ...
1
vote
1answer
84 views

Reordering algorithm for minimization of ram usage of a skyline matrix

The stiffness matrix of $Ax=B$ system of linear equations, where $A$ is an $n\times n$ symmetric matrix stored in the form of symmetric skyline matrix, that is associated with a finite element model ...
3
votes
1answer
39 views

Partial diagonalisation of large symmetric positive-definite band-diagonal matrices

I want to partially diagonalise real sparse symmetric positive-definite matrices, that are of dimension $n = 10^5$ and I need on the order of $k = 500$ of the smallest eigenvalues and eigenvectors. ...
9
votes
1answer
126 views

bit-packing and compression of data structures in scientific computing

I recently came across this paper, which describes a scheme for saving memory in representing sparse matrices. A 32-bit integer can store numbers up to ~4 billion. But when you solve a PDE you've gone ...
2
votes
0answers
68 views

Acceleration of matrix geometric series

Suppose we want to find $x$ such that: $$x=b+Ax$$ where $A$ is a large sparse square matrix with eigenvalues in the unit circle. There are two representations of the solution: 1) $$x=(I-A)^{-1}b,$$...
3
votes
0answers
71 views

Left eigenvectors using ARPACK

I'm trying to find both the dominant $k$ left and right eigenvectors, that is, $$V_L\mathcal{A} = \Lambda V_L\\ \mathcal{A}V_R = V_R\Lambda\\ V_LV_R = I_{k\times k}$$ $V_L$ being the $k\times N$ ...
5
votes
1answer
116 views

Can redundant variables be beneficial for root-finding convergence

Suppose I have $n$ generally nonlinear equations for $n$ variables, like e.g. for $n=2$ the system $F(x,y)=0$ $$ \begin{aligned} x^2+2y-4&=0\\ \sqrt{8}x+y^2-5&=0 \end{aligned} $$ By ...
1
vote
2answers
415 views

Which python library for GPU sparse linear system solver library

I have a fluid dynamic solver written in python which I want to accelerate by moving the most expensive computations to the GPU. Ideally all arrays and sparse matrices used in my code should remain on ...
0
votes
1answer
75 views

Matrix factorization empty rows and columns

I would like to do non negative mf and I wanna ask a question about my main matrix. The question is should I include rows and columns that have no non-zero entry in them. I think if there is not a ...
4
votes
2answers
127 views

Solve $Ax=b$ repeatedly where $A$ is a sparse weighted Laplacian matrix with changing weights

In the problem I am dealing with, I require to repeatedly solve $Ax=b$ where $A$ is a weighted Laplacian matrix of a sparse graph. The right-hand side remains constant. However each time I solve the ...
2
votes
2answers
246 views

Knapsack problem with fixed number of elements?

I am looking at an optimization problem that looks like this: $$ \text{minimize}\;\; \mathbf{x}^TQ\mathbf x \;\;, \; \mathbf x \in \mathbb R^n, x_i \in \lbrace 0, 1 \rbrace\\ \text{subject to}\;\; ||...
2
votes
1answer
138 views

MA57 vs HSL_MA57: symmetric indefinite solvers

What are the differences between MA57 and HSL_MA57 solvers? I'm in an optimization class that will make use of symmetric indefinite factorizations, and I'm trying to learn about the distinction ...
0
votes
1answer
58 views

Matlab backslash reordering algorithm

For the linear system $\mathbf A \mathbf x = \mathbf b$ generated from 2D Poisson equation using the standard central finite difference method, $$ \mathbf A = \begin{bmatrix} \mathbf K & -\mathbf ...
1
vote
1answer
126 views

More efficient matrix multiplication with diagonal matrix

A sparse matrix $\mathbf{L}$ is formed by $\mathbf{L} = \mathbf{DKG}$. $\mathbf{D}$ is a sparse matrix of size $m \times n$. $\mathbf{G}$ is a sparse matrix of size $n \times m$. $\mathbf{K}$ is a ...
3
votes
1answer
616 views

How can I speed up this code for sparse matrix-vector multiplication?

I've written a C++ function that multiplies a sparse matrix (stored in CSR format) by a dense vector. Here's the code: ...
1
vote
1answer
128 views

Data structure for efficient high dimensional histogramming

What data structure (or C++ library implementing it) is most suitable for efficient high dimensional histogramming? I have an application where I need to compute something similar to a histogram in a ...
5
votes
0answers
78 views

How to construct a eigensolver targeting a specific type of matrix

I need to diagonalize such kind of matrix during research: it's n-by-n, with it's upper-left (n-1)-by-(n-1) corner be diagonal while the nth row & column are dense. It's observed that the self ...
3
votes
2answers
157 views

Leveraging scipy for matrix free finite elements

This will be a very general question. I have a 3D finite element code in Python which I would like to extend to handle "large" problems (~10^8 unknowns in the global system). Right now I am using the ...
0
votes
1answer
73 views

How to do matrix operations with this way of storing sparse matrices

I read the way of storing the five or seven point laplace matrix for some poisson problem but I don't understand how can i multiply, add and subtract this stored sparse matrix by a vector or another ...
0
votes
1answer
80 views

Sparse matrix inverse with reduced bandwidth

I have a sparse symmetric matrix of dimension 1393x1393 (8308 no zero elements), with bandwidth 1380. By Cuthill–McKee algorithm, I could achieve a new matrix with ...
4
votes
1answer
276 views

Why is the speed of the parts of the LU-decomposition so different?

I know that an easy way to solve the matrix problem $$A\cdot x=b$$ is the LU decomposition $$\begin{split} L,\,U&=\text{lu}(A)\\ y&=\text{solve}(L,\,b)\\ x&=\text{solve}(U,\,y) \end{split}$...
1
vote
5answers
4k views

Fast c++ library to solve very big sparse systems

I am working on a project with electrical circuits, where I am trying to compute the voltages at all the nodes of an electrical circuit. I know that the electrical circuit is a perfect grid, so each ...
2
votes
2answers
2k views

Eigen - Max and minimum eigenvalues of a sparse matrix

I am working with an Eigen::SparseMatrix matrix of type double. I would like to find the largest and the smallest eigenvalues. A solution of the problem is to convert it to dense and then find its ...
1
vote
0answers
317 views

Pseudoinverse of a large sparse matrix in r

This question was moved from Cross-Validated: https://stats.stackexchange.com/questions/274042/pseudoinverse-of-large-sparse-matrix-in-r I am trying to calculate the pseudoinverse of a large sparse ...
2
votes
1answer
479 views

Which is the best subroutine available for solving sparse linear system of equations [closed]

I am trying to solve the system of linear equations: $AX=B$. For this currently I am using Intel MKL Pardiso solver. It works well when the order of $A$ is around $13500\times13500$ and below. Above ...
4
votes
2answers
439 views

Solving Ax = b with sparse A and sparse b

Let's suppose I'm numerically solving the Poisson equation for a delta function source: $$ \nabla^2 f(x) = \delta(x-x') $$ I can represent the Laplacian $\nabla^2$ using the finite difference method ...
1
vote
1answer
257 views

Compressed sensing: $\ell_0$ “norm” vs $\ell_1$ norm

Suppose we have a very efficient way to perform $\ell_0$ "norm" compressed vs $\ell_1$ norm compressed sensing. Specifically, $\ell_0$ "norm" compressed sensing is $$\eqalign{ & \min \quad {x^T}...
1
vote
0answers
55 views

Reduce large sparse linear operators to memory efficient loops?

I'm dealing a lot with large sparse linear operators these days and I'm quite new to them. A lot of the matrices I deal with originate with only a few unique integers, however, there are lots of them. ...