The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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.

132 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11
votes
0answers
462 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 ...
9
votes
0answers
189 views

Inverse problem in linear ODE

I have a linear ordinary differential equation (ODE) with a system matrix with constant coefficients: $$\dot{y}(t) = \mathcal{A}\; y(t), \quad y(0) = y_0$$ with $y(t) \in \mathbb{R}^{n \times 1}$ and $...
8
votes
0answers
181 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{...
8
votes
0answers
215 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 ...
7
votes
0answers
252 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, ...
6
votes
0answers
272 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 ...
6
votes
0answers
122 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
0answers
396 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
0answers
111 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
0answers
168 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=${$...
5
votes
0answers
166 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 -...
5
votes
0answers
150 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 ...
5
votes
0answers
142 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?...
5
votes
1answer
235 views

Robust smoothers for geometric multigrid

I'm searching for robust smoothers for geometric multigrids. By robust I mean: Effective for high order approximations (say spectral element, spectral Discontinuous Galerkin), Parallel (suitable for ...
4
votes
0answers
29 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, ...
4
votes
0answers
133 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...
4
votes
0answers
66 views

Complex differentiation of linear solvers

I have a linear system $$Ax=b$$ which I'm solving approximately, and I need to take the frechet derivative of x with respect to z. Were I solving the problem exactly (either analytically or to machine ...
4
votes
0answers
71 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 ...
4
votes
0answers
72 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 ...
4
votes
0answers
104 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 ...
4
votes
0answers
141 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 ...
4
votes
0answers
152 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 $$...
4
votes
0answers
98 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: ...
4
votes
0answers
607 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 ...
3
votes
0answers
83 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 ...
3
votes
0answers
70 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 ...
3
votes
0answers
144 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\...
3
votes
0answers
108 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 ...
3
votes
0answers
110 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 ...
3
votes
0answers
73 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 ...
3
votes
0answers
79 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 ...
3
votes
0answers
152 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 ...
3
votes
0answers
436 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 ...
3
votes
0answers
107 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$. ...
3
votes
0answers
155 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 ...
3
votes
0answers
413 views

full rank update to cholesky decomposition for multivariate normal distribution

This question is a specialization of full rank update to cholesky decomposition, to which I hope to get a more positive answer. When calculating the minus log of the multivariate normal distribution, ...
3
votes
0answers
364 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}]$ ...
3
votes
0answers
166 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 ...
3
votes
0answers
103 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 ...
3
votes
0answers
109 views

Up-/downdating methods for a series of normal equations

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 ...
2
votes
0answers
83 views

Small residual but wrong results

When I use BiCGStab to solve a linear matrix system, I use the relative residual to exit the iteration and output the results. For calculating the relative residual I divide the norm of vector $r$ ...
2
votes
0answers
37 views

Inverses of many standard subspaces of one large matrix

i have a large rectangular invertible matrix M (about 5000x5000) and i have a loop in which i do the following for each iteration i (there are about 6000 iterations): i am given a subspace S_i (which ...
2
votes
0answers
68 views

Regularized least squares with QR factorization

Consider the regularized least squares problem $$ \min_x || b - A x ||^2 + \lambda^2 ||x||^2 $$ which is equivalent to $$ \min_x \left|\left| \pmatrix{b \\ 0} - \pmatrix{A \\ \lambda I} x \right|\...
2
votes
0answers
356 views

Discrete-time Algebraic Riccati Equation (DARE) solver in C++

I need to use a Discrete-time Algebraic Riccati Equation (DARE) solver for an embedded controller (with limited processing power) in a research project and sadly, I can't find any implementation of it ...
2
votes
1answer
128 views

A Bound for the inverse of the sum of identity and triangular matrix

I wonder if there are any theorems which can help me to calculate an upper bound for the spectral norm of: $$\left\| \left[ I + \sum_{i=1}^{\overline{n}\in\mathbb{N}} \big( C_i - I\big)\right]^{-1}\...
2
votes
0answers
31 views

Randomized Submatrix of a Sparse Matrix

I have a sparse square matrix $A$ with size $n \times n$ and number of nonzero entries $nnz$. The goal is making a sub-matrix $B$ with $s$ nonzeros which are randomly chosen from $A$. Duplicates are ...
2
votes
0answers
68 views

Simultaneous update to barycenters

Suppose a tiling is given in 2D (an embedding of a planar triangulated graph), with all faces convex. Now suppose one moves each point, one by one, to the barycenter of its neighbors. I think that ...
2
votes
0answers
108 views

Efficiently solve linear system with matrix quadratic form

Take the system $$A^TCAx=b$$ where $$A\in\mathbb{R}^{n\times m},\;C\in\mathbb{R}^{n\times n},\;x,b\in\mathbb{R}^{m}, \;m\leq n$$ and $$A^TA=I$$ and $$Cy=d$$ can be solved efficiently in general (...
2
votes
0answers
80 views

Acceleration of matrix geometric series

Suppose we want to find $x$ such that: $$x=b+Ax$$ where $A$ is a large sparse square matrix with eigenvalues in the unit circle. There are two representations of the solution: 1) $$x=(I-A)^{-1}b,$$...
2
votes
0answers
96 views

Left eigenvectors using ARPACK

I'm trying to find both the dominant $k$ left and right eigenvectors, that is, $$V_L\mathcal{A} = \Lambda V_L\\ \mathcal{A}V_R = V_R\Lambda\\ V_LV_R = I_{k\times k}$$ $V_L$ being the $k\times N$ ...