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.
1,124
questions
2
votes
1
answer
214
views
Efficiently compute a projection matrix from Householders reflectors
Let $A \in \mathbb{R}^{m \times n}$ where $m \geq n$.
Let $B$ and $\tau$ be the result of applying LAPACK's dgeqrfp method (R on the upper right triangle, and the ...
3
votes
1
answer
215
views
A notion of resolution in inverse problems
Suppose I have a linear inverse problem of the form:
\begin{align}
Ax=b
\end{align}
I would like to reconstruct $x$ from the measurement $b$ via the objective
$$\min_x\{\vert\vert Ax-b\vert\vert^2_2+\...
- 725
1
vote
0
answers
151
views
Upper bound on condition number in linear preconditioning
I'm studying iterative methods for solving linear system, and I find the following setting in Wikipedia:
Consider a matrix splitting $A = M-N$, where $A,M,N$ are all symmetric and positive definite ...
- 11
6
votes
1
answer
541
views
Efficiently computing $e^{tX}$ for many different values of $t$
Given an anti-Hermitian and sparse matrix $X$, I am using Python (NumPy and SciPy) to compute the matrix exponential $f(t) := e^{tX}$ for many values of $t$. The method I am currently using is to ...
- 185
2
votes
1
answer
376
views
Numerical Linear Algebra: When to use Direct methods versus iterative methods to solve a linear system - for PDEs in particular
I am reading the Chapra and Canale book on numerical methods, and was working through the chapters on solving linear systems. Now the book goes through direct methods including Gaussian Elimination, ...
- 287
1
vote
0
answers
83
views
Given an unpivoted form of Aasen's algorithm, how does one add pivoting?
I've implemented the version of Aasen's algorithm described in the book Matrix Computations 4th Edition. The version there doesn't have pivoting. The book's description of how to add pivoting is a bit ...
- 161
2
votes
1
answer
61
views
How do I extract the output of Aasen's algorithm into a usable form?
I tried implementing the algorithm in Aasen's 1971 paper on factorizing symmetric indefinite matrices. I've translated the code verbatim from Algol into Python, and I used the test example given in ...
- 161
1
vote
1
answer
146
views
Complexity of solving an image differential linear system
Define an "image differential linear system" as a linear system $A\mathbf{x}=\mathbf{b}$ wherein $\mathbf{x}$ contains the ($\mathbb{R}$) pixels of an image and each row of $A$ constrains ...
- 255
6
votes
1
answer
1k
views
Parallelize Scipy iterative methods for linear equation systems(bicgstab) in Python
I need to solve linear equations system Ax = b, where A is a sparse CSR matrix with size 500 000 x 500 000. I'am using scipy.bicgstab and it takes almost 10min to solve this system on my PC and I need ...
- 161
6
votes
1
answer
216
views
Symmetric matrix which satisfies conditions of the form $v_i^T X v_i = 0$
I want to solve an underdetermined system of linear equations $A x = b$ with $A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. The matrix $A$ has the following additional ...
- 63
0
votes
0
answers
208
views
How to make a directed graph symmetric?
Say I have a directed graph given as an adjacency matrix $A$ in CSR format represented by the arrays ia (row indexes) and ja (...
- 544
3
votes
2
answers
130
views
Equations that are easier to verify than to solve?
Are there interesting examples of (systems) of equations where it is known to be harder to find a solution (in terms of scaling with respect to problem size) than verifying a provided solution for ...
- 2,273
1
vote
1
answer
293
views
Range of a matrix from its complete orthogonal decomposition
In this StackOverflow answer, @Gokul has shown how to get a basis of the kernel of a matrix with the help of the 'Eigen' function CompleteOrthogonalDecomposition. ...
- 283
1
vote
1
answer
449
views
Factorization of cubic spline interpolation matrix
In cubic spline interpolation, we use the set of knots and function values $(x_i,y_i),i=1,...,n$ to construct a (tridiagonal) system of equations for the unknowns $\sigma_i$:
$$
h_{i-1}\sigma_{i-1} + ...
- 544
0
votes
0
answers
66
views
Formula for overdetermined logical matrix pseudoinverse not requiring SVD?
In https://commons.wikimedia.org/wiki/File:YI_%3D_PI.png, you will find a formula-based solution for an overdetermined logical matrix pseudoinverse. This simple formula gives the same result as the ...
- 101
4
votes
1
answer
173
views
Trace of inverse from LU decomposition
Given an LU decomposition of $A\in \mathbb{R}^{n\times n}$, is there a way to compute $\operatorname{trace}(A^{-1})$ with lower complexity than that of the inversion ($O(n^3)$ in practice)?
This ...
- 11.1k
4
votes
0
answers
74
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}) = \...
- 41
7
votes
2
answers
392
views
Choice of iterative solver for a sparse asymmetric matrix with symmetric structure
I have a sparse $n\times n$ matrix $A$ with a pretty interesting structure. It has a block structure with a symmetric structure but asymmetric blocks. Expressed mathematically the block $A_{jk} = A_{...
- 2,069
2
votes
1
answer
293
views
Diagonalization of Hermitian matrices vs Unitary matrices
What are the general algorithms used for diagonalization of large Hermitian matrices and Unitary matrices? ($>5000 \times 5000$)
LAPACK seems to diagonalize Hermitian matrices almost 20 times as ...
- 133
2
votes
0
answers
85
views
Algorithm for computing inner products multiple times
I am taking a computational linear algebra course and i got stuck during a homework problem concerning the computation of inner products. I am supposed to compute the inner product:$$\mathrm{a}_{\...
- 121
4
votes
0
answers
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 ...
- 245
2
votes
1
answer
163
views
Efficient change of basis real positive definite symmetric matrix
I need to optimize a code where the most performance critical part is doing a 'change of basis', in other words it is an unitary similarity transformation on a big real positive definite symmetric ...
0
votes
0
answers
222
views
Ill-conditioned stiffness matrix
I am writting a Fem code in c++ for a 2d plane stress model. My question is regarding the assembly stiffness matrix.I noticed that some elements of the matrix are not exactly zero but insted a number ...
- 481
1
vote
1
answer
157
views
Jacobi iterative method
I'm using Jacobi iterative method for finding eigenvalue and eigenvector for hermitian or symmetric matrix. Eigenvectors corresponding to eigenvalues are not exact. The third eigenvector is totally ...
- 11
1
vote
0
answers
26
views
Multiplying by E[xy'] where only some statistics of xy' are known
(cross-posted on crossvalidated)
For random variable $(x,y)$ in $\mathbb{R}^{d}\times \mathbb{R}^{d}$ and vector $v \in \mathbb{R}^d$, I need to perform the following matrix vector multiplication.
$$T(...
- 2,273
5
votes
0
answers
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 ...
- 725
9
votes
2
answers
4k
views
When is it easy to invert a sparse matrix?
(Crossposted on cstheory.SE)
When is it easy to invert a sparse matrix? Specifically, I'm wondering about the cases in which matrix inversion has similar cost to sparse matrix multiplication, hence ...
- 2,273
2
votes
1
answer
51
views
Solving MX=N where M is structured as a Gaussian 4th-moment tensor
I'm looking to solve numerically the following equation for $(d,d)$ variable $X$, in Einstein summation notation
$$M_{ijkl}X_{kl}=N_{ij}$$
Where $M$ is a $(d,d,d,d)$ 4th-moment tensor of random ...
- 2,273
2
votes
1
answer
435
views
Ill-condioned Linear System and Gaussian Elimination
Suppose that I have a linear system $Ax=b$ such that $A$ is ill-conditioned. Can I say that it is dangerous to find a solution with Gaussian Elimination for this system, or does there exist some class ...
- 21
4
votes
2
answers
418
views
1D FEM for nonlinear diffusion coefficient
I want to solve with linear finite elements the equation $$\partial_t u = \partial_{x}(a(u)\partial_xu)$$
in the domain $t \in [0,1]$ and $x \in [-L,L]$. Here $a(u)$ is just a function of $u$.
...
- 309
3
votes
1
answer
121
views
Efficient solution to a structured symmetric linear system with condition number estimation
I have a real-valued linear system $Hx = b$ where $H$ is symmetric matrix** (not necessarily positive/negative definite) with a very particular structure:
$$
H = \begin{bmatrix} D && B \\ B^T &...
- 792
0
votes
0
answers
49
views
Norm estimates if adjoints can't be computed
Assume that you have two linear maps $A$ and $V$. For a given $x$ (of appropriate dimension) you can compute $Ax$ numerically, and for any $y$ (of appropriate dimension) you can calculate $V^Ty$ ...
- 1,738
7
votes
1
answer
1k
views
Cheap recalculation of eigenvalues and eigenvectors for a low-rank update of the matrix
Suppose I have a correlation matrix, $A$, and I already have the eigenvalues and eigenvectors of this matrix.
For a given vector, $\mathbf{\mathit{v}}$, I want to calculate the eigenvalues and ...
- 189
2
votes
1
answer
3k
views
Runtime of Gaussian elimination/row reduction on a rectangular $m \times n$ matrix
The runtime of Gaussian elimination on an $n \times n$ matrix is $O(n^3)$. What is the runtime on an $m \times n$ matrix?
I am taking Gaussian elimination to mean putting the matrix in reduced row ...
- 23
1
vote
1
answer
205
views
Frobenius norm of a binary matrix
In term of the mathematical distance measurement,
What is the significance of a Frobenius norm for a binary matrix?
- 31
1
vote
1
answer
472
views
How to optimize nuclear norm subject to positive semidefinite constraints?
For finite dimensional symmetric positive semidefinite matrices $A$ and $B$, I would like to solve
\begin{align}&\min |X - A|_1 \\
&\text{subject to}\\
&X \preceq B \\
&0 \preceq X\...
- 113
0
votes
0
answers
84
views
Derivative-free ill-conditioned non-linear least squares
I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as ...
- 131
9
votes
4
answers
865
views
Checking singularity of a matrix
Suppose that we don't know $n \times n$ matrix $A$ explicitly but we are only able to compute products $Ax$ where $x$ is a column vector with $n$ elements. Is there an algorithm to determine whether $...
- 331
1
vote
3
answers
541
views
How to determine global stiffness matrix is constrained or not
Background
In solid fem, we often solve $$\mathbf{Ku}=\mathbf{p}$$
where $\mathbf{K}$ is global stiffness matrix, $\mathbf{u}$ is displacement, $\mathbf{p}$ is global load vector.
If displacement not ...
- 323
2
votes
1
answer
260
views
Efficient projection of a vector onto matrix kernel
Given an $m \times n$ matrix $A$ and a vector $x\in\mathbb R^n$, with $m<n$, what's an efficient way of computing the projection of $x$ onto the kernel of $A$?
- 1,729
8
votes
2
answers
600
views
Is there an iterative solver for dense matrices with possible zero diagonal entries?
Is there an iterative solver that can handle potentially zero entries on the central diagonal? I am implementing a polynomial fitting algorithm (up to $10^{th}$-order) and my matrix is a "...
- 233
2
votes
2
answers
984
views
Solution of the linear system using Sherman-Morrison formula for 1000000x1000000 (7450.6GB) matrix using MATLAB
Let $n = 10^6.$ Let $A \in \mathbb{R}^{n\times n} $ be the lower triangular matrix having 1's on and below the main diagonal.
We want to solve the following linear system:
$$ (A + uv^T)x = b$$
by the ...
user36184
3
votes
0
answers
746
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 ...
- 661
3
votes
0
answers
102
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 ...
3
votes
0
answers
100
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 ...
- 31
5
votes
1
answer
198
views
Accurately Computing a Positive Vector in the Nullspace of a Matrix
I'm sure this question has been asked before yet after many hours of searching I am unable to find a definitive answer.
The problem at hand is solving the linear system: $$A \mathbf{x} = \mathbf{0}$$ ...
- 53
0
votes
0
answers
332
views
A parallelized GMRES solver?
My application calls for solving a dense, 40,000 x 40,000, ill-conditioned linear system. The native SciPy GMRES solver with preconditioning has worked well for my application and solving a single ...
2
votes
0
answers
126
views
Why is LAPACK (seemingly) suboptimal for packed and banded eigenvalue problems?
Based on this LAPACK routines list, it looks like there is no relatively robust representation (RRR) driver routine for either packed or banded symmetric eigenvalue problems. According to the relevant ...
- 201
8
votes
3
answers
639
views
Is LAPACK behind the cutting edge of dense linear algebra?
I have been digging into some numerical linear algebra lately, and reading in particular about how LAPACK solves symmetric eigenvalue problems. I noticed that the ...
- 201
1
vote
2
answers
451
views
Why OpenFOAM uses its own data structures and linear solvers?
I wonder why OpenFOAM code has its own data structures Lists, HashTables, ... etc. when there is the STL in C++?
Another ...
