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

**10**

votes

**0**answers

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

**7**

votes

**0**answers

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

**5**

votes

**0**answers

92 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

133 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

**0**answers

100 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

163 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

**0**answers

78 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

445 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

187 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

**0**answers

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

**2**

votes

**0**answers

189 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

161 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

52 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

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

**2**

votes

**0**answers

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

**1**

vote

**0**answers

73 views

### How to fit a stochastic matrix to given data.?

Given a data sequence of noisy observations of a 3-state Markov chain $X$ -- $y_1$,$y_2$,...$y_n$, with two transition matrices $A_1$ and $A_2$ corresponding to different regions (**) in the (unit) ...

**1**

vote

**0**answers

83 views

### How to solve a divergent linear system using iterative methods?

I have a matrix A which is symmetric and non-diagonal dominant. I tried to use Jacobi/Gauss-Seidel/SOR to solve it but it diverges. Is there any mechanism to condition the matrix for convergence using ...

**1**

vote

**0**answers

160 views

### The rationale of QR algorithm for computing eigenvectors

For a symmetric matrix $A$, the rationale for the success of applying QR to compute the spectral decomposition of $A = UDU^T$ is, for large $k$, the QR factorization of $A^k = Q_kR_k$ obeys,
...

**0**

votes

**0**answers

104 views

### Global and local maxima in a weighted sum of logarithms of linear functionals?

Constrained Optimization Problem
Is is possible to describe, and locate efficiently, the maxima of the function $f$, as described below in the parameters $\mathbf{x} = (x_1,...,x_m)$. The constraints ...

**0**

votes

**0**answers

106 views

### Hadamard / matrix product adjoint

First of all I would like to thank everyone over here at mathoverflow for their amazing generosity and help (for both pros and newbies like myself).
I apologize if this question seems dumb; I'm a new ...

**0**

votes

**0**answers

52 views

### Bits of precision matrix reconstruction

We have a real rank $r$ matrix $M\in\{0,1\}^{n\times n}$.
Suppose we have diagonalized using $LMR=D$.
I want to recover a real matrix $\widetilde{M}$ such that maximum absolute entry of ...

**0**

votes

**0**answers

65 views

### Way to parameterise sparse multi diagonal matrix

I have an NxN matrix S that looks like this: $$ S^{-1} = K^{-1} + \Lambda $$
where N is a multiple of 3, both K and S are positive definite matrices, and Lambda is
$$
\Lambda = \begin{bmatrix}
x ...

**0**

votes

**0**answers

29 views

### Column Subset Selection implementations

Are there readily available implementations of algorithms for the CSSP - Column Subset Selection Problem?

**0**

votes

**0**answers

125 views

### Finding peaks and determining noise

Hello ,
Im having one matrix which is product of two FFT transforms of one fits image ( astronomical image ). In that matrix you could find 3 peaks. One largest in center, and two around central ...