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

213 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
707 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 ...
229 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 293 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 281 views ### Stable alternatives to "condition number"? A number of numerical problems are easy to solve when condition number$\kappa$of the problem is low. For instance, conjugate gradient descent complexity scales as$O(\sqrt{\kappa})$. However "... 8 votes 0 answers 426 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, ... 8 votes 0 answers 769 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, ... 7 votes 0 answers 84 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 135 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 333 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 326 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 ... 6 votes 0 answers 508 views ### Is there any catch on using zgemm3m vs regular zgemm? I've just (to my embarrassment) encountered a BLAS-like extension of a matrix-matrix product subroutine gemm in Intel MKL: gemm3m... 6 votes 0 answers 134 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 140 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 193 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=${$... 135 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 ...
201 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 ...
144 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 ...
97 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 ...
130 views

76 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 ...
543 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 ...
100 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 ...
135 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 ...
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 ...
214 views

143 views

### Estimating the spectral radius when applying the method of lines

Some time integrators, notably the Runge-Kutta-Chebyshev method, implemented in the RKC code from Sommeijer & Verwer, gives the user an option to provide a callback with an estimate of the ...
117 views

### When would one choose un-pivoted $LDL^T$ instead of $LL^T$ for a Positive Definite Matrix?

Background I am decomposing (and then operating on) a symmetric positive definite matrix (a covariance matrix) as part of a larger system. Dimensions range from O(10) to O(300). The covariance ...
71 views

### Approximating eigenvalues of DPR1 matrix with special properties

In my application, I have a sum of diagonal $A$ and rank-1 $B$ $$T=\underbrace{\text{diag}(1-2\alpha h+2\alpha^2 h^2)}_A + \underbrace{\alpha^2 hh^T}_B$$ Where $h$ is a vector $\in \mathbb{R}^d$ with ...
77 views

### Householder Vector algorithm in Golub and Van Loan

(This is repost of a question first asked on Mathematics. Hopefully there are more people here who have a copy of Golub and Van Loan to hand) In the 4th edition of "Matrix Computations", ...