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

**10**

votes

**0**answers

188 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

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

91 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

91 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

144 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

51 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

29 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

401 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

120 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

180 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

168 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

151 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

51 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

145 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

473 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

70 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

79 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

154 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

85 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

96 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

51 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

56 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

24 views

### Column Subset Selection implementations

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

**0**

votes

**0**answers

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