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

188 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
638 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 ...
210 views

Problem Solving a non-linear system of equations. The number of variables is the same as the number of equations. When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{... 9 votes 0 answers 273 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 ... 8 votes 0 answers 396 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, ... 7 votes 0 answers 61 views ### Choice between using Moore-Penrose inverse and G2 inverse Moore-Penrose inverse for an arbitrary matrix$X\in \mathbb{R}^{n \times p}$is defined by a matrix$X^\daggersatisfying all of the Moore-Penrose conditions, namely \begin{align} (1) \;\;\;& XX^\... 7 votes 0 answers 102 views ### Can we sparse solve a few eigenvalues specified by index range? I need to solve a few eigenvalues of a large sparse matrix specified by their index range. These indices are according to the whole eigenspectrum sorted in algebraic (not absolute value) ascending ... 7 votes 0 answers 288 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, ... 7 votes 0 answers 309 views ### Compute sparsity pattern ofA^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 ... 7 votes 0 answers 683 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, ... 6 votes 0 answers 128 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 ... 6 votes 0 answers 120 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 ... 6 votes 0 answers 181 views ### Find the solution of linear equation using Wiedemann/ Krylov method Let given$M =$1 0 1 0 1 1 1 1 1 and$b =$1 0 1 How to find the solution$x_3$where$x=${$... 121 views

### Why are fast Givens rotations mentioned so little in the recent literature?

Fast Givens rotations seem like a nice upgrade from standard Givens rotations. They take fewer multiplications to apply and avoid the calculation of a square root. They are, however, given very little ...
172 views

### Inverse problem with uncertain forward operator

Suppose I want to solve a linear inverse problem. In this example we take a convolution with the kernel: $$\frac{1}{(y^2+z^2)^{3/2}}$$ We only take a fixed $z$ for the computation and convolve with ...
140 views

### Explanation of subspace strategy regarding CG described in Golub's book

I was wondering about the last paragraph in Matrix Computations (4th edition) by Golub, Chapter 11 (11.3.3), specifically his explanation of subspace strategy for Conjugate Gradient. Note that in ...
93 views

### Trying to understand splitting-based iterative method for 2D Laplace problem

I am trying to understand the theory behind a splitting based iterative method which uses the incomplete Cholesky factorization. Before giving the specific details, let me first give the problem ...
102 views

71 views

### Optimize linear equation using inner products and subject to L1 norm

I have a linear system of the form $A x = b$ where $A$ and $b$ are known, $A$ is "square", and $\lvert b \rvert_1 = \lvert x \rvert_1 = 1$. Unfortunately, I am working in a framework that ...
445 views

### Fastest matrix library for Android (with GPU is possible)

I was working on an Android app that requires some linear algebra with matrices. The matrices will be somewhat medium-sized as they are not too small or too big. I was originally using jBlas because ...
92 views

### Block matrix and DSYRK

I want to compute the matrix $$A = \sum_{i=1}^N v_i v_i^T$$ where each $v_i$ is a given vector of length $2500$, so that $A$ is $2500 \times 2500$, and my $N$ is about 2 million. Rather than call ...
131 views

### How to stochastically estimate the trace of a matrix?

Specifically, the diagonal elements (can possibly both positive and negative) of the matrix can be computed efficiently but the total number is large ($\mathcal O(10^{18})$). My first thought about ...
295 views

### Rank-one Update to a Rank Revealing QR (RRQR) Factorization?

Suppose we are given an RRQR factorization for some matrix $A \in \mathbb{R}^{m \times n}$, $A\Pi = QR$ where $m > n$. Is there a cheap way to update $A' = A + uv^{\top}$ given this factorization?...
1k 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 ...
194 views