# Questions tagged [linear-algebra]

Questions on the algorithmic/computational aspects of linear algebra, including the solution of linear systems, least squares problems, eigenproblems, and other such matters.

152 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
504 views

### Fast Eigenvalue and SVD Solver for Structured Matrices

I am looking for a fast Eigenvalue and SVD solver for small dense structured matrices (Hankel and Toeplitz). I have searched for efficient implementations in libraries like MKL but I am not able to ...
263 views

305 views

### Eigenvalue with largest imaginary part

Iterative eigensolvers such as ARPACK, give the option to find a subset of the eigenvalues which have the largest imaginary part. My question is how do these algorithms work. As I understand it, ...
242 views

### Wanted: sequences of linear systems for recycling Krylov solver analysis

In the solution of sequences of linear systems $$A_ix_i=b_i\quad\text{for}\quad i=1,2,\dots$$ with Krylov subspace methods, data can be recycled from already solved linear systems in order to speed up ...
67 views

### Implementation of Lanczos method that returns tridiagonal matrix

The Lanczos method can be used to obtain extremal eigenpairs of sparse symmetric or hermitian matrices. I know there are several implementations of the Lanczos method (as well as Arnoldi, Davidson, ...
281 views

### Compute sparsity pattern of $A^2$

Suppose we have a sparse matrix $A$. Is there any way to compute just the sparsity pattern of $A^2 = A \cdot A$ (I do not actually need to know what exactly the nonzero value are) faster than to ...
125 views

### What strategies / decompositions would be useful to solve the following linear system repeatedly if I only care about time to solution?

Let $A\in \mathbb{R}^{n\times n}$ be symmetric positive semidefinite, and $B\in \mathbb{R}^{n\times n}$ be symmetric positive definite. Suppose $B$ is block diagonal so it is easy to invert. (We ...
478 views

### What is the source of the error in the Sherman-Morrison formula application?

The Sherman-Morrison formula $$(A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$$ results in small errors in relation to the standard matrix inverse operation after each application, ...
115 views

### How does an unpivoted QR fail to reveal rank?

An unpivoted QR factorization produces a triangular factor $R$. A rank-revealing QR factorization is typically done with column pivoting. My question is, how does an unpivoted QR factorization fail to ...
170 views

157 views

### Unstable convergence of a Poisson equation

What could be the reason that the solution of a Poisson equation is smooth when obtained by an iterative solver, only if the maximum residual is set to a high value (e.g. 0.1)? When the maximum ...
133 views

### Iteratively solving a sparse, ill-conditioned system

I have a sparse (density = 0.2%), ill-conditioned system that I am trying to solve, with no luck. Background I have a sequence of sampled data, where two of every 8 samples have been zeroed due to a ...
82 views

### Backward stable algorithm to get orthogonal projection onto the column space of a matrix

I have to find the orthogonal projection of a vector $b$ onto the matrix $A$ of size $m \times n$. In my application, I don't have the luxury of calculating the QR factorization. All I have are ...
82 views

### Computing Algebraic Riccati inequality

In my Robust model control, I have got a couple of quadratic Riccati inequalities which need to be solved numerically on MATLAB. My question, Is there function on MATLAB can solve quadratic Riccati ...
170 views

### Eigenvalues with absolute values close to 1

I have a generalized eigen-problem: $A\psi = \lambda B \psi$ with $A$ and $B$ are large (>1000) complex non-Hermitian matrices. I know that eigenvalues with largest and smallest absolute values can be ...
608 views

### Fixing a near singular covariance matrix

Given a near singular covariance matrix, the standard method of 'fixing' it seems to be to add a small damping coefficient $c>0$ to the diagonal, which serves to bump all the eigenvalues up by this ...
109 views

### Conjugate gradient: the 1-norm of the residual

I am trying to solve $Ax=b$ using the conjugate gradient method. However, it is important to me to obtain a bound not only on the usual residual $||b-Ax_k||_2$ but also on the quantity $||b-Ax_k||_1$. ...
170 views

### Find constrained vectors maximizing angles between them - methods?

This is related to a question I had asked earlier, with the distinction that earlier I did not have a non-linear objective functional to minimize. The problem is reproduced below with added ...
380 views

### On solution of a class of discrete-time Lyapunov equation for systems with multiplicaitve noise

Let's consider the following equation $$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$ where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment $F=[F_{1}...F_{p}]$ ...
169 views

### How to accurately decompose positive semidefinite matrix and use the lower triangular part in linear equations

I have $n$ arbitrary $p\times 1$ vectors $x_i$, and $p\times k$ matrices $A_i$, and $n$ $p \times p$ positive semidefinite matrices $S_i$, where some (often most) of the $S_i$'s are same (for example ...
104 views

### Efficient principal pivots

It was suggested I should try posting this question here from Mathematics Background I'm working on a numerical linear algebra package in C#. I'm trying to implement a variety of "principal ...
In an application I have to solve a series of positive definite linear systems of the form $A^TA x = A^Tb$ (i.e. normal equations). The next system is obtained from the previous one by adding and/or ...