# 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].

135 questions
Filter by
Sorted by
Tagged with
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 ...
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$). ...
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 ...
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 ...
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$...
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 ...
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 ...
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 ...
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 ...
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 ...
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 & ...
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 &...
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 ...
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 ...
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 ...