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.

179 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
605 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 ...
198 views

111 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 ...
152 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 ...
139 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 ...
92 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 ...
95 views

70 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 ...
363 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 ...
89 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 ...
129 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 ...
259 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?...
948 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 ...
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 $$... 0answers 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: ... 0answers 177 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 ... 1answer 130 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_{... 0answers 289 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 ... 0answers 72 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 ... 0answers 92 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 ... 0answers 199 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 ... 0answers 44 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 ... 0answers 103 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 ... 0answers 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 ... 0answers 304 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\... 0answers 230 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 ... 0answers 159 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 ... 0answers 242 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$ ...
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 ...