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

**11**

votes

**0**answers

202 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

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

**7**

votes

**2**answers

498 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

**1**answer

1k 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

1k 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

**3**answers

4k 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

166 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

175 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

**0**answers

184 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

112 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} ...

**6**

votes

**2**answers

325 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

528 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, ...

**5**

votes

**3**answers

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

**5**

votes

**2**answers

953 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

**2**answers

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

**5**

votes

**1**answer

183 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

**0**answers

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

**5**

votes

**0**answers

135 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

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

**4**

votes

**1**answer

84 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

153 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

388 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}
...

**4**

votes

**0**answers

106 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

176 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

1k 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

**4**answers

555 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 |$

**3**

votes

**2**answers

171 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

834 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

**2**answers

449 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\\
&& ...

**3**

votes

**2**answers

162 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, ...

**3**

votes

**1**answer

190 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

80 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

62 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 + ...

**3**

votes

**0**answers

88 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, ...

**3**

votes

**0**answers

32 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

465 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

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

**2**

votes

**2**answers

321 views

### Solving a matrix equation $X=c \cdot AXA' +I$ with a diagonal corrections

I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation:
$X=c \cdot AXA' - diag(c \cdot AXA')+ I$,
where
(1) $A \in R^{n \times n}$ is a given matrix whose element ...

**2**

votes

**2**answers

210 views

### Probability for a random positive-semidefinite matrix to not be positive-definite?

If I take $A^TA$, where $A$ is a full-rank random matrix (let's say with Gaussian-distributed independent entries), can I expect it to be positive-definite? It will be positive semi-definite ...

**2**

votes

**2**answers

157 views

### Inflate a simplex, change rows to make the rank n

I have a simplex, n + 1 points in $\mathbb{R}^n$,
which may have rank $r < n$.
Is there a cheap way of "inflating" it to rank $n$,
changing a few, all but $r$, of the points ?
The points are ...

**2**

votes

**1**answer

324 views

### A question for solutions of perturbed linear systems

Consider a linear system
$$Ax=b\qquad (*)$$
and a sequence of perturbed linear systems $$(A+\delta A_n)x=b+\delta b_n. \qquad (n)$$
Suppose that all the linear systems are consistent (i.e., ...

**2**

votes

**2**answers

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

**2**

votes

**1**answer

125 views

### Updating $LU$ decomposition after adding a sparse matrix

How many elements of $LU$ decomposition of a symmetric matrix change after adding a sparse symmetric matrix? Is it more efficient to recompute $LU$ decomposition after adding a sparse matrix comparing ...

**2**

votes

**1**answer

81 views

### Numerical solution of singular ODE

Consider the singular ODE
$y''+\frac{y'}{r}+p(r)y=0 \ \ with \ \ y(0)=1 \ \ and \ \ y'(0)=0$.
Theoretically such solution exists and is unique if $p$ is nice. Is there a method to numerically ...

**2**

votes

**0**answers

202 views

### What would be a better method for numerical diagonalization of a certain Vandermonde-like matrix?

For the fractional iteration of the $\exp()$-function Hellmuth Kneser had 1942 proposed an analytic solution valid on the real numbers; there is a technical implementation for Pari/GP of this method ...

**2**

votes

**0**answers

171 views

### Error bound on matrix vector multiplication

I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate.
Some (a very small fraction) of the element's value is changed from $a_{i,j}$ to {0,$-a_{i,j}$, $2a_{i,j}$}. ...

**2**

votes

**0**answers

54 views

### Most efficient algorithm for computing norm of the residual for the least squares problem in the rank deficient case

I have a large $m\times n$ data matrix $A$, $m>n$, and response $m$-vector $b$. I need to calculate $E = ||Ax-b||_2$ as quickly as possible, where $x$ is the least squares solution. I don't need ...

**2**

votes

**0**answers

149 views

### Checking for error in conjugate gradient algorithm

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...