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
13 votes
0 answers
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 ...
user avatar
9 votes
0 answers
210 views

Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system

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{...
user avatar
  • 163
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 ...
user avatar
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, ...
user avatar
  • 243
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^\dagger$ satisfying all of the Moore-Penrose conditions, namely \begin{align} (1) \;\;\;& XX^\...
user avatar
  • 173
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 ...
user avatar
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, ...
user avatar
  • 171
7 votes
0 answers
309 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 ...
user avatar
  • 71
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, ...
user avatar
  • 170
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 ...
user avatar
  • 1,000
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 ...
user avatar
  • 4,420
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=${$...
user avatar
5 votes
0 answers
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 ...
user avatar
5 votes
0 answers
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 ...
user avatar
  • 720
5 votes
0 answers
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 ...
user avatar
  • 161
5 votes
0 answers
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 ...
user avatar
5 votes
0 answers
102 views

Levinson Recursion for Non Square Toeplitz Matrices

Given a rectangular Toeplitz Matrix $ H $, how could one solve: $$ y = H x $$ For instance, $ H $ can be Linear Convolution Matrix of the filter $ h $: $$ H = \begin{bmatrix} {h}_{1} & 0 & ...
user avatar
  • 298
5 votes
0 answers
64 views

Nonlinear least squares optimized Jacobian calculation

I have a nonlinear least squares problem, in which I am trying to minimize residuals which can be divided into four classes: $$ \min_x ||\epsilon(x)||^2 + ||\xi(x)||^2 + ||\delta(x)||^2 + ||s(x)||^2 $$...
user avatar
  • 956
5 votes
0 answers
194 views

Solving $AXB + X\odot C = D$ matrix equation

Can anyone see a way to solve this equation efficiently? $$AXB + X\odot C = D$$ I tried a straightforward solution that involved vectorizing $X$ but that turned out too expensive for my application -...
user avatar
5 votes
0 answers
391 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...
user avatar
  • 8,451
5 votes
0 answers
85 views

Improving convergence of Jacobi iteration to Schur form

I'm using SIMD processor arrays to compute the eigen-decomposition for large numbers of small (up to $32\times 32$) matrices. For assorted technical reasons, Jacobi iteration maps well to the SIMD ...
user avatar
5 votes
0 answers
155 views

Multi-matrix orthogonal basis problem

Suppose we are given a set of symmetric, positive definite matrices $A_1,A_2,\ldots,A_k\in\mathbb{R}^{n\times n}$. Is there any numerical method or reduction to a known problem (e.g. eigenvalue ...
user avatar
5 votes
0 answers
223 views

Preconditioning technique for large sparse non-hermitian matrix

I am attempting to solve a computational acoustics problem that involves solving an underlying sparse matrix. The size of the problem varies with grid size (3D) and fill-in's obviously make direct ...
user avatar
5 votes
0 answers
751 views

Perron-Frobenius theorem on general real symmetric matrices

From the Perron-Frobenius theorem, it might be concluded that the spectral radius is the largest eigenvalue for positive matrices, ie, matrices with strictly positive entries. In other words, the ...
user avatar
  • 1,633
4 votes
0 answers
79 views

Decomposing a banded matrix

Suppose we have a linear algebra problem with a banded matrix A which has nonzero entries on the main diagonal, two nearest sub-diagonals, and two other sub-diagonals (such band structure often arises ...
user avatar
4 votes
0 answers
132 views

Stable iterative solver for complex symmetric linear systems

I am interested in the iterative solution (preferably Krylov-type solvers) of a problem $\boldsymbol{A}x=b$, with $x,b\in\mathbb{C}^{n\times1}$ and $\boldsymbol{A}\in\mathbb{C}^{n\times n}$. $\...
user avatar
  • 141
4 votes
0 answers
83 views

Unstable Algorithms which become stable when hardware provides Kulisch exact dot product instruction

In John Gustaffson's book The End of Error, he discusses Ulrich Kulisch's exact dot product, which (in double precision) requires a 2100 bit fixed point register which rounds only once after the ...
user avatar
  • 2,021
4 votes
0 answers
78 views

Check if LinearOperator is symmetric

I have a scipy.sparse.linalg.LinearOperator object. I'd like to check if its associated matrix is symmetric without actually instantiating the matrix in the most ...
user avatar
  • 203
4 votes
0 answers
61 views

Efficient computation of marginalized multivariate normal likelihood

In general,if we know that the marginal Gaussian distribution for some variable $\textbf{x}$ and a conditional Gaussian distribution for some $\textbf{y}|\textbf{x}$ of the forms: $$p(\textbf{x}) = \...
user avatar
4 votes
0 answers
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 ...
user avatar
  • 245
4 votes
0 answers
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 ...
user avatar
4 votes
0 answers
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 ...
user avatar
  • 956
4 votes
0 answers
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 ...
user avatar
4 votes
0 answers
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?...
user avatar
  • 41
4 votes
0 answers
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 ...
user avatar
  • 443
4 votes
0 answers
194 views

Galerkin FEM error when using even number of elements

Intro: I am developing a Galerkin FEM code in matlab - starting small with a simple 1D ODE. The equation I'm trying to solve is: $$a u_x = cos(x), x \in [0, 2\pi]$$ Which has a known exact solution $$...
user avatar
4 votes
0 answers
101 views

Tracking for two meshes

I'm dealing with physical simulation (position based dynamic). Now I'm trying to realize tracking for two meshes. In order to explain what does it mean, let's assume that we have two similar meshes: ...
user avatar
3 votes
0 answers
54 views

Sparse generalized symmetric eigensystem solver

Can anyone recommend a good software for solving generalized symmetric eigenvalue problems of the form, $$ A x = \lambda B x $$ where $A,B$ are symmetric and sparse, and $B$ is positive definite? I ...
user avatar
  • 956
3 votes
0 answers
422 views

Jacobian Matrix of 2D element mapped to 3D

Note: I previously posted this question to MathStackExchange, but got no attention there. So I'm rewritting and trying over here. Problem summary Given a common¹ set of shape functions defined at ...
user avatar
3 votes
1 answer
169 views

Choice of iterative solver for a sparse asymmetric matrix with symmetric structure

I have a sparse $nxn$ matrix A with pretty interesting structure. It has a block structure with symmetric structure but asymmetric blocks. Expressed mathematically the block $A_{jk} = A_{kj}$ but $A_{...
user avatar
  • 1,902
3 votes
0 answers
427 views

Compute Nullspace of Sparse Matrix

I am computing the nullspace of a sparse rectangular $m$ x $n$ matrix $A$, where $m$ << $n$. I do this by computing the QR decomposition of $A^T$ and extract the $n-m$ right-most columns of the ...
user avatar
  • 576
3 votes
0 answers
82 views

Numerical calculation of the Berry connection

I'm doing some numerical calculations involving Hermitian matrices, and derivatives of the eigenvectors. Essentially, I have an n x n, Hermitian matrix H(x), which is dependent on some continuous ...
user avatar
3 votes
0 answers
93 views

Is the matrix exponential and the Jordan canonical form actually useful for solving differential equations?

All of my yearlong graduate-level Linear Algebra course notes from my professor—an algebraist/representation theorist—shows his love for the exponential map $e^A$ and the Jordan canonical form—and one ...
user avatar
3 votes
0 answers
227 views

What is the fastest algorithm for computing log determinant of a PSD matrix? (All possible PSD matrices)

I am diving into some literature to understand which is the best algorithm for computing the log-determinant of a PSD matrix. More generally, I am interested in a list of resources to read, which ...
user avatar
  • 131
3 votes
0 answers
45 views

Subspaces for Iterative methods

In the original paper of Conjugate Gradients, the authors mention that if we pick the canonical basis $\{e_1,e_2,\ldots,e_n\}$, to obtain A-orthonormal vectors, we end up with the Gaussian elimination ...
user avatar
  • 171
3 votes
0 answers
109 views

Why the MIRACLE of Lanczos/CG-like?

Lanczos/Arnoldi/Rietz/CG-like algorithm share the same core strategy... In each, a little miracle appears, most of the Gram-Schmidt inner products are zeroes! In others words, new direction need only ...
user avatar
  • 57
3 votes
0 answers
85 views

Element Preconditioner

Im just working on a preconditioner for the linear equation system $Ax = b$ arising in FEM for elliptic PDE. $A$ is a s.p.d Matrix with real valued entries. I read something about the element by ...
user avatar
3 votes
0 answers
366 views

Computing Small Eigenvalues with Sparse Symmetric Indefinite Mass Matrix

I want the eigenvalues of the following generalized eigenvalue problem: $$ Av = \lambda M v $$ where $A\in\mathbb{R}^{n\times n}$ is sparse, symmetric, and positive semi-definite $M\in\mathbb{R}^{n\...
user avatar
3 votes
0 answers
244 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 ...
user avatar
  • 31
3 votes
0 answers
164 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 ...
user avatar
  • 131