{numerical-linear-algebra} questions involving algorithms for linear algebra computations.

**28**

votes

**9**answers

12k views

### Fast Matrix Multiplication

Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in $...

**11**

votes

**2**answers

557 views

### Determinant and eigenvalues of a specific matrix

This came up in a conversation with an engineer friend of mine.
Let $c>0$ be a constant. Let $A_{ij}$ be an $n$ by $n$ matrix with entries
$$
A_{ij} = e^{-c(i-j)^2}.
$$
Is there a name for this ...

**11**

votes

**0**answers

219 views

### What are the difficulties in proving almost-everywhere stability of Gaussian elimination?

It is well known that Gaussian elimination without pivoting is numerically unstable, and in practice Gaussian elimination is done with row pivoting (partial pivoting). A theorem of Wilkinson states ...

**10**

votes

**2**answers

283 views

### Why Householder reflection is better than Givens rotation in dense linear algebra?

It’s obvious that Givens rotation works better with sparse matrices. But I don’t know why Householder reflection is better for dense matrices. Does it require less computations? Or it’s numerically ...

**8**

votes

**1**answer

260 views

### Efficiently compute the trace of a sparse matrix times the inverse of a sparse matrix?

How can I efficiently compute
$\mathrm{trace}(A(B^{-1}))$
where $A$ and $B$ are both sparse symmetric PSD $n \times n$ matrices, both with $O(n)$ non-zero entries? If it helps, the pattern of non-...

**7**

votes

**2**answers

2k views

### efficient rank-two updates of an eigenvalue decomposition (or more genearlly SVD)

Let $A$ be a symmetric matrix with eigenvalue decomposition $UDU^T$. Golub, et al. and Bunch, et al. have shown that given such an $A$, the eigenvalue decomposition of $A+\rho xx^t$ may be computed ...

**7**

votes

**2**answers

557 views

### polynomials with minimal $L_\infty$ norm on multiple disjoint intervals

It is well-known that Chebyshev polynomials are the polynomials of minimal $L_\infty$ norm on [-1,1] with leading coefficient 1. But what if you want the minimal $L_\infty$ polynomial on two disjoint ...

**7**

votes

**2**answers

238 views

### How to estimate a specific infinite matrix sum

Let $M$ be an $n$ by $n$ matrix with each diagonal element equal to $k$ and each non-diagonal element equal to $k-1$ where $n$ and $k$ are positive integers. Let $k < n$ and we can assume both $k$ ...

**7**

votes

**2**answers

2k views

### Finding the smallest eigenvalues 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 $M$. $M$ is a Laplacian matrix, and it has the following structure: $...

**7**

votes

**1**answer

648 views

### The singular values of the Hilbert matrix

The $n\times n$ Hilbert matrix $H$ is defined as
$H_{ij} = \frac{1}{i+j-1}, \qquad 1\leq i,j\leq n$
What is known about the singular values $\sigma_1\geq\ldots\geq \sigma_n$ of $H$?
For example, ...

**7**

votes

**3**answers

5k views

### Interesting relationships between Cholesky decomposition and diagonalization

Let $\Sigma$ be a hermitian positive definite matrix and $L$ be it's Cholesky decomposition so that $LL^\ast=\Sigma$. Furthermore, let's diagonalize $\Sigma$ as $\Sigma = P\Lambda P^\ast$. $\Lambda$ ...

**7**

votes

**1**answer

78 views

### Add a multiple of $I$ to a matrix to minimize its operator norm

Given $A\in\mathbb{C}^{n\times n}$, what is $s_* = \arg\min \|A-sI\|$?
Here $\|A\|$ is the operator norm, $\|A\|=\rho(A^*A)^{1/2}$, and $I$ is the identity.
The corresponding problem for the ...

**7**

votes

**1**answer

170 views

### Compute only selected components of an eigenvector

I am wondering whether it is possible to compute portions of the eigenvectors of a given (possibly very big) matrix. More formally, consider the eigenvalue problem $\mathbf{Ax} = \lambda \mathbf{x}$, ...

**7**

votes

**1**answer

197 views

### Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?

Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...

**7**

votes

**2**answers

2k views

### Eigenvectors of a symmetric positive definite Toeplitz matrix

I wish to efficiently compute the eigenvectors of an n x n symmetric positive definite Toeplitz matrix K. A full eigendecomposition would be even better.
Although I assumed this would be a well ...

**7**

votes

**0**answers

203 views

### Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method.
In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...

**7**

votes

**0**answers

110 views

### How do I find elements of an algebra which generate an algebra contained in a fixed subspace?

Suppose $V$ is a linear subspace of a finite dimensional $C^*$-algebra $A$. (Feel free to assume $A$ is a multi-matrix algebra over $\mathbb C$.)
I would like to find $x \in V$ such that $\mathbb C [...

**6**

votes

**3**answers

123 views

### Algorithm to quickly compute the individual inverses of a linear sequence of matrices

Fix $n \times n$ real symmetric positive definite matrices $A$ and $B$. Fix vectors $x$ and $y$ in $\mathbf{R}^n$. I want to compute the following bilinear products quickly: $\{x^T (A+mB)^{-1} y\}_{m=...

**6**

votes

**2**answers

265 views

### A system of non-linear equations that is decomposable as a product — uniqueness of solution?

I have a system of non-linear equations
$ a_1=f_0 g_1$
$a_2=f_1 g_1 + f_0 g_2$
$a_3=f_2 g_1 + f_6 g_2 + f_0 g_3 $
$a_4=f_3 g_1 + f_7 g_2 + f_6 g_3 + f_0 g_4 $
$a_5=f_4 g_1 + f_8 g_2 + f_7 g_3 + ...

**6**

votes

**2**answers

570 views

### Conditions for convergence of Euler's method

It is known that a sufficient and necessary condition for
$$\dot y(t) = f(y(t), t), \quad t > 0, \quad y(0) = y_0$$
to have a unique solution is $f$ Lipschitz in $y$ and continuous in $t$. However, ...

**6**

votes

**1**answer

189 views

### For a set of matrices $S$, find $X$ such that the elements of $SX$ commute

Let $S := \{A_0, A_1, \dots, A_d\}$, where $A_k \in \mathbb{C}^{n \times n}$, be a set of (generally noncommuting) matrices. I am interested in finding a nonsingular $X \in \mathbb{C}^{n \times n}$ ...

**5**

votes

**2**answers

796 views

### Linearly constrained eigenvalue problem

Suppose I'd like to:
\begin{align}
\mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\
\text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\
&& \...

**5**

votes

**3**answers

283 views

### Norm of triangular truncation operator on rank deficient matrices

Let $T_{n\times n}$ be a triangular truncation matrix, i.e.
$$T_{i,j}=\begin{cases}1 & i\ge j\\ 0 & i<j \end{cases}$$
It is known that for arbitrary $A_{n\times n}$
$$\|T\circ A\|\le\frac{\...

**5**

votes

**2**answers

1k views

### Factorizing a block symmetric matrix

Let $X,Y\in\mathbb{R}^{n\times n}$ be symmetric matrices. You may assume that $X$ is positive semidefinite and $Y$ negative semidefinite, if needed, but not that they are invertible.
I would like to ...

**5**

votes

**0**answers

79 views

### Tensor matricizations and their decompositions

Suppose we have a 4-index tensor $t_{ijkl}$ (all 4 dimensions are equal size). We can make a matrix out of it by taking first and last two indexes as new indexes: $t_{ijkl} \rightarrow M_{ij, kl}$. ...

**5**

votes

**0**answers

95 views

### Inverses of the sums of all possible subsets of a set of symmetric and positive definite matrices

I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e.
$(A_1+A_2)^{-1},(A_1+A_3)^{-1},(A_2+A_3)...

**5**

votes

**0**answers

137 views

### reference for perturbation of projection result

Let $A$ and $B$ have the same rank and dimensions. If $P_A$ denotes the projection onto the range space of $A$, then
$$
\|P_A - P_B\|_2 \leq \|A - B\| \cdot \min (\|A^\dagger\|_2, \|B^\dagger\|_2).
$$
...

**4**

votes

**4**answers

666 views

### Determinant of sum of Kronecker products

Given four real symmetric matrices $A,B \in \mathbb{R}^{n \times n}$ and $C,D \in \mathbb{R}^{m \times m}$, is there an efficient way to compute the determinant:
$\det|A \otimes C + B \otimes D |$

**4**

votes

**2**answers

2k views

### Is there some algorithms for solving non-linear matrix equations?

Is there some algorithms for solving non-linear matrix equations on field $\mathbb{C}$?
Especially, solving polynomial nonlinear matrix equations.
For instance, let $X$ be some matrix satisfying
$X=...

**4**

votes

**1**answer

96 views

### Behaviour of eigenspaces of adjacency matrices after a single change to the graph

Say I know the eigenvalues and eigenvectors of an adjacency matrix of an unweighted graph. Can I say anything about the eigenvalues and eigenvectors of an adjacency matrix of a graph with one extra ...

**4**

votes

**2**answers

188 views

### QR-Decomposition of matrix valued function

Suppose I have a matrix valued function
$$
F:\mathbb{R}\rightarrow\mathbb{R}^{m\times n},\qquad F(x)=\tilde Q\tilde R+xu_1v_1^T+xu_2v_2^T
$$
where $\tilde Q\in\mathbb{R}^{m\times m}$ is orthogonal, $...

**4**

votes

**1**answer

93 views

### Sensitivity of the range of a matrix

The distance between two subspaces $\mathcal{U}$ and $\widetilde{\mathcal{U}}$ is classically defined as $d(\mathcal{U},\tilde{\mathcal{U}}):=\|P-\tilde{P}\|$, where $P$ and $\tilde{P}$ are orthogonal ...

**4**

votes

**1**answer

166 views

### standard practice for large dense truncated svd computations?

What are the standard methods of computing the rank-k truncated SVD of large dense matrices? My literature search yields results only for large sparse matrices.
I assume for k small that you use a ...

**4**

votes

**1**answer

455 views

### Norm of inverse confluent Vandermonde matrix

Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as
$$V=
\begin{bmatrix}
v_{1,0}&v_{2,0}&\dots&...

**4**

votes

**0**answers

117 views

### Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form:
\begin{equation}
A =
\left[\begin{array}{c|c}
\...

**4**

votes

**0**answers

197 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 -...

**3**

votes

**2**answers

2k views

### Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix?
The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...

**3**

votes

**2**answers

183 views

### What are interesting heuristics of determining how far given matrix is from a singular one?

The condition number and volume of matrix (defined as absolute value of its determinant) are things which come to mind. Is there more?
I think that over the years numerical folks (who are faced with ...

**3**

votes

**1**answer

962 views

### Nonlinear matrix equation

Solve the following nonlinear equations for $v$ and $w$
$Avv^TAw=\lambda_1v+\lambda_2w$
$Aww^TAv=\lambda_1w+\lambda_2v$
$v^Tw=w^Tv=0$
$v^Tv=w^Tw=1$
where $\lambda_1, \lambda_2, \lambda_3$ are ...

**3**

votes

**1**answer

117 views

### The spectral norm of the truncated exponential of a matrix

Let $A$ be a matrix satisfying $A^*+A\leq0$, it can be shown that $\|e^{tA}\|_2\leq1$ for all $t\geq 0$, where $\|\cdot\|_2$ is the spectral norm defined as largest singular value of the matrix.
I am ...

**3**

votes

**1**answer

246 views

### submatrix of a given size with maximum frobenius norm

Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...

**3**

votes

**1**answer

84 views

### Conjugate gradient algorithm where first search direction is not equal to residual

In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact ...

**3**

votes

**0**answers

84 views

### Finding nearest Toeplitz matrix to a given matrix

For an arbitrary $N\times N$ Hermitian matrix $A$, I want to derive a Toeplitz matrix from $A$ such that the eigenvectors of both matrices have minimal change.
Specifically I want find the Toeplitz ...

**3**

votes

**0**answers

107 views

### Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, i.e.,...

**3**

votes

**0**answers

34 views

### Quasi-M matrices?

Does any body know a reference on lower triangular matrices with negative entries everywhere except for the diagonal and subdiagonal where entries are positive (when all entries are negative with ...

**3**

votes

**0**answers

557 views

### Quantifying the failure of the Cholesky factorization test for indefinite matrices

The Cholesky factorization is the classic test to check if a matrix is positive definite. In infinite precision it is also an exact test: A matrix has a Cholesky factorization iff it is positive ...

**3**

votes

**0**answers

121 views

### Computing the norm of the columns of an implicitly defined matrix

I have an $n \times n$ matrix $M = \Sigma W$ where $\Sigma$ is diagonal and $W$ orthogonal. $W$ is implicitly defined, i.e. I can only perform matrix-vector products (but I also have access to $W^T$).
...

**3**

votes

**0**answers

192 views

### Could SVD be used to optimize the partial inner-products?

Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...

**3**

votes

**0**answers

648 views

### How many iterations are required for the Lanczos algorithm to converge?

I am trying to find the n smallest eigenvalues and eigenvectors of a NxN SPD matrix using Lanczos method. What is the number of iterations usually required? I mean, does it scale as $O(N)$ or $O(\sqrt{...

**2**

votes

**2**answers

241 views

### Matrix, singular values, Moore-Penrose-pseudoinverse

If A is any real mxn-matrix consider the block matrix
$\begin{pmatrix} E&A^T \\ A&0\end{pmatrix}$. This matrix seems to have close connections with pseudo inverse, svd etc. which are probably ...