Questions tagged [sparse-matrices]

Use this tag for questions regarding sparse matrices, that is matrices with relatively few entries compared to their size. Related: [numerical-methods] and [numerical-linear-algebra].

Filter by
Sorted by
Tagged with
0
votes
1answer
13 views

Solve banded linear system with large bandwidth but sparse interior band structure

Assume the linear system $Ax = b$, where $A$ is a $N \times N$ banded matrix with lower and upper bandwidth $l$, and $N >> l >> 1$. $A$ has the following structure: All entries of $A$ are ...
1
vote
0answers
60 views

Inverse a sparse matrix

I have a sparse singular matrix W where I want to find its inverse Q. My current method is to use $W*Q = I$ for an optimization process of approximating the convergence of cost function norm($I-W*Q$). ...
1
vote
1answer
29 views

Fast algorithms for long sequences of sparse matrix products multiplying a vector?

Context: Having worked with developing algorithms involving huuge linear least squares systems involving sparse matrices, so far I have mostly constructed these huge sparse matrices explicitly and ...
0
votes
0answers
15 views

Condition value of sparse matrix

I have a sparse matrix really ill-conditionned. I wondered if the places where the non zero values have an impact on the condition value. My matrix is PSD and what I'd like to know is if the condition ...
0
votes
0answers
23 views

Expressing OneHotEncoding as a linear algebra operation

In ML applications dealing with categorical variables, it is often required to transform them into a OneHotEncoded representation. For example, given a vector of categorical features, $x=(1,3,4,2,3)^T$...
0
votes
0answers
11 views

What can be said about the LU decomposition of matrices with the same sparsity pattern?

Consider a set of invertible matrices $A_i$, each with an LU decomposition $$ A_i = L_iR_i $$ or with partial pivoting $$ P_iA_i = L_iR_i $$ What can be said about the sets $L_i$, $R_i$, $P_i$? Is ...
0
votes
1answer
33 views

Vector density as a function of sparsity

Many works denote $\phi(x)$ as density of a vector. $$ \phi(x) = \frac{||x||_1^2}{d||x||_2^2} $$ where $x \in \mathbb{R}^d$. Can we say that this quantity decreases as we increase sparsity? For ...
1
vote
0answers
16 views

What is the complexity of determining the eigenvalues of a very sparse matrix?

Suppose I have an $n \times n$ matrix with $O(n)$ nonzero elements. With what time complexity could the eigenvalues or characteristic polynomial of this matrix be computed? More easily, suppose I ...
1
vote
1answer
32 views

Can the Thomas algorithm be used to solve banded matrices of any arbitrary size? (ie larger than tridiagonal, penta/septa/+diagonal systems)

I am working a product concerning the Poisson Equation. In this project, I end up with a very large square matrix. It's impossible to solve efficiently with simple Gaussian elimination, but the matrix ...
6
votes
2answers
260 views

General formula for $f(n)$

Let for $n\geq 3, C_n$ denote the $(2n) \times (2n)$ matrix such that all entries along the diagonal are $2$, all entries along the sub- and super-diagonal are $1$, all entries along the antidiagonal ...
1
vote
0answers
95 views

How to evaluate directly the determinant? [duplicate]

How does evaluate the determinant of the following $(2n+1)\times (2n+1)$ matrix? \begin{equation} \det A = \begin{array}{|cccccccccc|cc} 1 & -1 & 0 & \dots & 0 & ...
2
votes
2answers
111 views

How to determine direct solution of determinant?

How to show that the determinant of the following $(2n+1)×(2n+1)$ matrix $A$? \begin{equation} \det A = \begin{array}{|cccccccccc|cc} 1 & -1 & 0 & \dots & 0 & 0 &...
0
votes
0answers
22 views

How to “fill in” a 2d grid based on neighbors

I've got an array of elevations on a plane, but there are missing values. Specifically it is elevations I derived from lunar satellite data regarding the south pole. I'd like to use the data to make ...
0
votes
0answers
29 views

Largest matrix you can calculate eigenvectors of

Apologies if this isn't the correct place to post this (couldn't decide between here and stack overflow). For an 'average' computer, I want to determine what the largest matrix whose eigenvectors one ...
0
votes
1answer
56 views

The inverse of a sparse triangular matrix

I am solving a sparse system of linear equations $Ax=b$, where $A$ is symmetric positive definite. My matrix is 3210 x 3210, with about 10 non-zero values per row. For a specific $A$, I will need to ...
1
vote
1answer
23 views

Multiplication of columns of matrix appended with identity matrix

I have a matrix $A \in \mathbb{R}^{n\times n}$. Let $\{a_1,a_2,\ldots,a_n\}$ be its columns. I want to find the product of the matrices $A_1 \times A_2 \times\dots \times A_n$ where $A_i=[e_1 \quad ...
0
votes
0answers
34 views

Effective way to calculate the $ \sum_{j}^{} N_jZZ^TN_j^Tx $

I am looking for a most efficient way to calculate $\sum_{j}^{} N_jZZ^TN_j^Tx $ whereas $ N_j,Z \in \mathbb{R}^{nxn}$ $j \in \mathbb{N}, j=1,2,3,..$ and x is a corresponding vector. j is finite ...
0
votes
0answers
27 views

Universal Approximation Theorems for Sparse Networks

It is well-known, as shown in Hornik's papers, that feed-forward neural networks are dense in the spaces of continuous functions (uniformly on compacts) and the spaces of $L^p$ functions (for suitable ...
0
votes
0answers
39 views

Eigenvalues of sparse matrix

I want to calculate the eigenvector corresponding to the $0$ eigenvalue of a large, sparse singular matrix. However, if I try eigs(A,1,'smallestabs'), MATLAB has an ...
1
vote
0answers
42 views

Eigenvector of large sparse stochastic matrix

I have a large sparse matrix corresponding to a system of master equations for a continuous-time Markov chain. It's approximately $500,000 \times 500,000$, with a density of around $10^{-6}$. Is ...
0
votes
0answers
27 views

Gradient descent and graphical lasso

I was looking into the graphical lasso algorithm and saw that the update is being carried out via block coordinate descent. I wanted to know whether or not gradient descent can be used for the same? ...
2
votes
2answers
103 views

Diagonalization of very large (but very simple) sparse matrix

I have a $10^5 \times 10^5$ matrix and I need its smallest eigenvalue (not the the smallest in absolute value, but actually the lowest) and the associated eigenvector (I know the eigenvalue to be non-...
2
votes
0answers
77 views

Need to solve a linear system with a sparse n x n matrix

I am developing an application in C# language — an electric simulator that uses the node-voltage method in the AC frequency domain. I need to solve large systems of linear equations (over $\mathbb C$)...
1
vote
0answers
23 views

How to generate random sparse unitary with given density?

For my research, I need to generate sparse (complex-values) unitary matrices at random from a uniform distribution. It is not a problem for me to generate the generic unitary matrices using, e.g., ...
0
votes
0answers
23 views

How to solve linear system with sparse large matrix?

I have the following system that I need to solve. The matrix is large $n \times n$, where $n = Nz* Nr \approx 150000$ or larger. The matrix always has the following form: Just 5 diagonals at $Nz, 1, 0,...
1
vote
0answers
31 views

How to recover sparse circulant matrix based on its partial eigenvalues?

Suppose we have a right circulant matrix ($n \times n$) $$ C= \begin{bmatrix} c_0 & c_{n-1} & c_{n-2} & \cdots & c_1\\ c_1 & c_0 & c_{n-1} & \cdots & c_2\\ ...
0
votes
0answers
15 views

Sparse orthogonal cycle basis

I was looking for references to the following problem: Let $G$ be an undirected, unweighted graph. We're interested in finding a sparse, orthogonal cycle basis for $G$. The motivation from this ...
0
votes
1answer
26 views

Cholesky solve for semi-definite system

I am thinking about the following linear algebra problem: $$ Ax = b $$ where $A$ is an $n$ by $n$ positive semi-definite matrix, in particular, it is rank $n-1$ with null space span$\{e=(1,1,\ldots,1)^...
1
vote
1answer
141 views

compute $C = AB^{-1}A^T$ without inverting B

Is it possible to compute $C = AB^{-1}A^T$ without computing the inverse of $B$ explicitly? A is $n \times m$ matrix. B is $m \times m$ matrix ($m \gg n$). Thus $C$ is much smaller than $B$. In the ...
0
votes
0answers
30 views

Over-complete dictionary and sparse basis selection optimisation problem

I am trying to solve the following problem: Given the matrix $T \in \mathbb{R}^{D \times N}_{\geq 0}$, find matrices $U \in \mathbb{R}^{D \times K}_{\geq 0}$ and $W \in \mathbb{R}^{(D+K) \times N}_{\...
1
vote
0answers
56 views

Symmetric sparse matrix inversion

I have the impedance matrix Y, formulated from an electrical network by augmented nodal analysis. The matrix Y is shown as an image to illustrate its feature visually, where all the white blocks are ...
0
votes
1answer
366 views

Inverse of a large sparse matrix in Matlab

Background: Let $\Omega$ be the state space of an absorbing Markov chain with $\Omega_a$ being the set of absorbing states, and its complement $\Omega_a^c$, being the set of transient states. The ...
1
vote
1answer
72 views

Does a sparsified correlation matrix follow the Perron Frobenius theorem?

Consider an N x N correlation matrix which has been sparsified to retain only the sqrt(N)*N highest elements. It has the following characteristics: - Sparse - Non-negative (values are positive real ...
0
votes
1answer
17 views

Estimating sparse precision matrices - penalised likelihood method

In order to estimate sparse precision matrices, there is a method called "penalised likelihood" which leads to this formula. Can someone write down the demonstration ? I do not understand how we ...
0
votes
1answer
116 views

Inverse of symmetric matrix that is almost diagonal

I have an $N\times N$ matrix $\mathbb X$ with entries: $$X_{ij} = x_i\delta_{ij} + y_i(\delta_{i+m,j}+\delta_{i,j+m})$$ where $1 \le m \le N$, and $x_i,y_i$ are given numbers. Is there an ...
3
votes
1answer
147 views

Inverse of a symmetric tridiagonal matrix

I have a symmetric $n\times n$ matrix $\mathbb A$ with entries: $$A_{ij} = (a_i + a_{i-1})\delta_{ij} - a_i\delta_{i,j-1}-a_{j}\delta_{i-1,j}$$ where $a_0,\dots,a_n$ are given positive numbers. Is ...
1
vote
0answers
51 views

Eigenpairs of a sparse symmetric block tridiagonal matrix with diagonal blocks on the outer diagonals

I'm looking at methods to find the eigenpairs of symmetric block tridiagonal matrices, with sparse blocks on the main diagonal and diagonal blocks on the outer diagonals. Has any research been done on ...
0
votes
1answer
26 views

Is there a formula to identify valid positions in an upper triangular matrix?

not a maths major, just a programmer unable to solve the following dilemma: I have an upper triangular matrix of size NxN, so for example with N being 4, a 4x4 matrix with 16 positions such that if ...
3
votes
3answers
507 views

Solve this specific large sparse system of linear equations

I want to solve the system $Ax = b$ where $A \in \mathbb R^{n \times n}$ and $b \in \mathbb R^n$ with $n \approx 10^6$. If $A$ would be a fully dense matrix this would be hopeless of course but ...
0
votes
0answers
25 views

Ax=b Clustering

I came across a very common multi-modal robustness problem. I have a simple linear equation set $Ax=b$ that I need to solve. Obviously, SVD can be used for a least-squares solution for $x$. ...
0
votes
1answer
230 views

fast linear solvers

I have a linear system $Ax=b$ that is solved in each time step of a code. the point is that matrix $A$ is constant. only the right hand side $b$ is changing every time step. matrix $A$ is sparse with ...
6
votes
1answer
114 views

Fast way to Invert ADA' when D is a diagonal matrix that changes each iteration?

So I have a statistical learning algorithm in which D is a diagonal matrix that changes each iteration while A stays the same. I'm looking for a fast way to invert ADA' each iteration which ends up ...
1
vote
1answer
52 views

How to optimize a non-linear least squares energy with respect to the non-zeros of a sparse matrix?

I have an energy I'd like to minimize of the form: $E(G) = \|\underbrace{X - Y G^T L G B}_{f(G)}\|_F^2$ where $X,Y,B$ are dense matrices and $G,L$ are sparse matrices ($G^TLG$ is also sparse), $\|M\...
2
votes
1answer
302 views

How to compute amount of floating point operations for LU-decomposition of banded matrix?

I want to compute the amount of floating point operations, flops, needed for the LU-decomposition/factorization of a banded matrix A consisting of 5 nonzero diagonals. Matrix $A\in\mathbb{R}^{n \...
1
vote
3answers
116 views

Is $det(A)=0$ a good indicator to say that a matrix is not invertible?

In finite elements, for example, appears huge sparce (CRS) matrices (matrices with a lot of zeros). It is possible that matlab (or some other program) calculates $det(A)=0$ even though the matrix is ...
1
vote
0answers
35 views

An alternate for Householder QR linear equation solving for fixed-layout sparse matrix

This concerns sparse matrices where the sparsity pattern is known beforehand, and where the size is between 5 and up to 50, as the linear solver for a Newton Raphson non linear solver. For smaller ...
1
vote
2answers
562 views

Generating a random sparse hermitian matrix in Python

I'd like to find a way to generate random sparse hermitian matrices in Python, but don't really know how to do so efficiently. How would I go about doing this? Obviously, there are slow, ugly ways to ...
3
votes
0answers
46 views

Where can I find 'Emily', the matrix visualization tool?

While searching for a tool to visualize sparse matrices I discovered this paper about 'emily', a piece of software which has everything I need. However, I cannot find a place to download or purchase ...
0
votes
1answer
88 views

Sparse recovery with L1 shrinkage iteration for higher denominational image classification

For 2 months I have been studying sparse recovery and its applications for image classification and I have found that it's a broad area in mathematics which gives rise to a wide variety of ...
0
votes
1answer
881 views

time complexity for sparse matrix multiplication $XX^T$

I have an matrix $X\in R^{m\times n}$ and the matrix is very sparse. Assume the $nnz(X) = D$, which means the number of non-zero elements is $D$, then what is the time complexity to compute $$A = ...