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
4
votes
1
answer
119
views
Rank-1 correction of matrix exponential
I need to approximate the following in $O(d)$ time for $d\times d$ diagonal $A$ and rank-1 $B$
$$u^T \exp(-A+B) v$$
Here $u,v$ are vectors in $\mathbb{R^+}^d$, $A,B$ are positive semi-definite and $B$ ...
- 2,273
2
votes
0
answers
102
views
Schur complement formulation of linear system
Consider a system of the following form:
$$(A+K)x=b$$
where $A$ is symmetric, positive definite and block diagonal (in fact, a block diagonal matrix made of stiffness matrices arising from FEM ...
- 157
5
votes
1
answer
206
views
How to optimize an approximated matrix multiplication?
[UPDATING]
The old one is a simplified version of the current one. Here is a solution based on the answer proposed by professor Bangerth down below. To describe what I am trying to do, first rewrite ...
- 55
1
vote
1
answer
83
views
Powers of convergent DPR1 matrices in $O(d)$ time?
Suppose $u$,$v$ are vectors and $A$ is a convergent $d\times d$ diagonal + rank-1 matrix.
How do I estimate $u^T A^k v$ in $O(d)$ time?
Powers of convergent diagonal $D$ can be computed in $O(d)$ time ...
- 2,273
4
votes
2
answers
232
views
Faster than forward substitution?
I have a matrix of the form:
$M:=\begin{pmatrix}
S_1 & & & \\\ Q_1 & S_2 & & \\\ & ... & ... & \\\ & & Q_n & S_n\end{pmatrix}$
where the blocks ...
- 157
3
votes
0
answers
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 ...
- 2,273
7
votes
1
answer
352
views
Computing powers of diagonal + rank-1 matrix?
I'm using a numeric root-finder to find $k$ satisfying $\|A^k x\|=c$ where $A$ is a symmetric $d\times d$ diagonal + rank-1 matrix. How to compute $A^k x$ efficiently?
For integer $k$, I can get the ...
- 2,273
0
votes
0
answers
58
views
Eigenvalues of same operator expressed in two different orthonormal basis are coming out different
I have an operator $H$. I express $H$ as a matrix in the orthonormalized $\{ |e > \}$ basis. Then I diagonalize it to obtain eigenvalues, let's say for example $H$ is $6 \times 6$ and the ...
- 31
2
votes
1
answer
101
views
Ways to fix block Lanczos tridiagonalisation numerical instability for matrix with degenerate, closely spaced eigenvalues?
I want to run a block Lanczos block-tridiagonalization on a hermitian, sparse matrix (of relatively small size $\sim 10^2 \times 10^2$). However the matrix typically has many eigenvalues that are ...
- 21
1
vote
1
answer
158
views
Lanczos memory complexity for dense matrices
Does the Lanczos algorithm remain memory efficient even if the original Hermitian matrix is dense?
- 11
1
vote
0
answers
62
views
Does the choice of a complex inner product affect Krylov methods?
As far as I understand there are two definitions of the complex inner product:
$$(a,b) = b^H a$$
and
$$(a,b) = a^H b$$
I know some linear algebra libraries such as BLAS and Eigen uses the second one.
...
1
vote
0
answers
43
views
FEM Basis for functions of two variables in $\mathbb{R}^2$ (Applied to Linear Full Stokes Equations)
I'm trying to do FEM for a very basic version of the linear full Stokes equations in two dimensions. Say we are working in the grid $[0,1]\times[0,1]$ in the $xy-$plane.
To solve an FEM problem for a ...
- 111
6
votes
1
answer
215
views
Inverse power iteration and solving singular system
The algorithm for the inverse power iteration works as following :
\begin{align}
&v^{(0)} =\text{ some vector with }\|v^{(0)}\|=1\\
&\text{for }k = 1, 2, \ldots\\
&\qquad\text{Solve } (A - ...
- 169
3
votes
0
answers
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", ...
- 181
2
votes
2
answers
216
views
How can I express the solution to a discrete Lyapunov equation as an eigenvalue problem?
Given the discrete Lyapunov equation $$AXA^T - X + Q = 0$$ how can I solve for $X$ as a function of the eigenvectors of some matrix $H$?
More precisely, in the case of the continuous Lyapunov equation ...
- 165
2
votes
0
answers
112
views
Starting point to use Trilinos linear algebra packages?
I have experience with classical linear algebra packages in C++ like Eigen, Blaze, etc.
I have never wrote my own PetSC back-end solver but I used/modified several of them.
In a new project I would ...
- 21
1
vote
0
answers
108
views
What's the best modern algorithm for recursive least squares?
Recursive least squares can be implemented using the Sherman–Morrison formula to avoid resolving, however, have better methods without $n^2$ cost been developed? I'm interested if there is a good ...
- 111
3
votes
0
answers
104
views
Compute orthogonal complement using BLAS / LAPACK
Is there a fast method to compute an orthogonal complement of an arbitrary matrix $U\in\mathbb{R}^{m \times n}$ in BLAS / LAPACK?
Specifically, I want any matrix $V\in \mathbb{R}^{m \times (m - \text{...
- 799
0
votes
0
answers
33
views
Effect of a flipped image on projection matrix and the intrinsic/extrinsic calibration matrices
I already asked this question on StackExchange Mathematics, but it seems too domain-specific. Searching where to put Computer Vision related questions it was suggested to use Computational Science ...
- 101
2
votes
0
answers
47
views
Software for Smith form or Hermite form of a sparse polynomial matrix
In a current research project, I have a number of matrices with coefficients in ℚ[𝑥] for which I want to understand how their rank depends on the value of the parameter 𝑥.
These matrices are:
...
3
votes
1
answer
87
views
Reuse linear mapping that provides the solution to least squares problem using LAPACK
LAPACK.gglse allows me to solve
min x^T Q x
s.t. A x = y
(in my present use case, $Q$ is symmetric positive definite)
without having to think about the numerical ...
- 799
0
votes
1
answer
153
views
How to efficiently transpose distributed matrix in Scalapack?
I have a distributed matrix in block cyclic layout. Is there an efficient way to out/in place transpose a distributed matrix with scalapack?
Context: I am trying to diagonalize the transpose of a ...
- 103
4
votes
0
answers
83
views
Can you left-precondition least squares?
Suppose I want to solve an overdetermined linear least squares problem
$$
x = \operatorname*{argmin}_{x\in\mathbb{R}^n} \| Ax - b\|^2
$$
where $A \in \mathbb{R}^{m\times n}$ has full column rank. I ...
- 350
6
votes
1
answer
214
views
Why FEM for incompressible materials is ill-posed?
I am an engineer who is trying to get a deeper understanding of FEM. I have been using the Zienkiewicz texts as my bible. It touches on the issue of incompressibility but I need a more intuitive way ...
- 201
0
votes
0
answers
45
views
Rectangular problem to use for benchmarking a large dense linear solver?
Can anyone suggest a rectangular problem I can use for evaluating a large dense linear solver? ($m,n>1000$) IE, ideally something that's easy to download and has been evaluated for some solvers ...
- 2,273
1
vote
0
answers
59
views
Guaranteeing that the numerical approximation to $B = K^{-T}K^{-1}$ is positive definite in Zhang's algorithm
In Zhang's Algorithm to determine the intrinsic parameter matrix $K$ (see here for slides talking about this), we instead compute the matrix $B = K^{-T}K^{-1}$ since we obtain a linear system in the ...
- 19
11
votes
2
answers
307
views
What makes a good preconditioner when only a few approximate iterations are needed?
For deterministic solver of $Xw=y$, one recommendation is to pick $P$ such that $P^{-1}X$ has a low condition number. However, this condition only really matters when you want to reduce initial error ...
- 2,273
3
votes
2
answers
861
views
Why does this preconditioner effectively reduce the condition number of a random SPD matrix?
Consider some randomly generated matrix $B\in\mathbb{R}^{100\times100}$ and let $A:=BB^{\top}$
On MATLAB I computed the condition number of $A$, I obtained a value of $2.8377\mathrm{e}+04$
However if ...
- 133
1
vote
0
answers
112
views
Does cblas_dgemm mutate my input matrices?
I have written a matrix class Matrix<T> for which I have implemented a wrapper function for cblas_dgemm.
...
- 111
2
votes
0
answers
52
views
Finding spectrum of a Kronecker factored + block-partitioned matrix
I have dense $d\times d$ matrices $A$, $B$, $C$ with $d\approx 1000$ and want to find the top $10^5$ eigenvalues of the following positive definite matrix:
$$
\Sigma=
\left(\begin{matrix}
A\otimes A &...
- 2,273
2
votes
0
answers
65
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 ...
- 1,048
2
votes
1
answer
372
views
Matrix regularisation for ill-conditioned problems
I have read that matrix regularisation can improve the stability of LU or Cholesky decomposition of ill conditioned problems. The idea is to add a value to the diagonals of a matrix:
$B=A+cI$
In the ...
- 840
4
votes
2
answers
154
views
Numerical estimation of eigenfunctions of Laplacian
Consider the Laplace equation,
$$
\nabla^2 f(r,\theta,\phi) = 0
$$
in spherical coordinates. We know that the solution to this equation can be derived analytically, and is given by,
$$
f(r,\theta,\phi)...
- 1,048
7
votes
1
answer
282
views
Which preconditioners make Richardson iteration convergent?
Suppose we solve an $m\times n$ full-rank system of equations $Ax=b$ by iterating the following for a small enough $\mu>0$
$$x=x+\mu B(b-Ax)$$
Is there a nice description of kinds of $B$ which make ...
- 2,273
3
votes
1
answer
146
views
Column-normalized inverse?
Suppose we define $A^{*}$ of positive definite $A=X'X$ using following two steps:
let $B=A^{-1}$
scale columns of $B$ to obtain a matrix with $1$'s on the diagonal
For the case of singular $A$, we ...
- 2,273
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^\dagger$ satisfying all of the Moore-Penrose conditions, namely
\begin{align}
(1) \;\;\;& XX^\...
- 173
2
votes
1
answer
121
views
Numerical representation of linear spaces
A linear space in mathematics is a set whose elements (vectors) have operations of addition and multiplication by a scalar defined in such a way that certain properties are satisfied (commutativity, ...
- 2,440
9
votes
2
answers
2k
views
Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?
I have a system of conductors for which there are two dense matrices of the (complex) mutual admittances, $Y_A$ and $Y_B$, which are symmetric. Then, an equivalent nodal admittance matrix $Y_N$ is ...
3
votes
1
answer
164
views
Using submatrices of matrix decomposition for solving a large number least-squares problems
I want to decrease the computational time for solving a large number (>1000) of least-squares problems. Given a matrix, the system matrix for each least-squares problem is a submatrix of the given ...
- 219
1
vote
1
answer
165
views
constructing a symmetric matrix for finite difference
I come across the following operator in a paper
$\mathcal{I}\psi = \psi_{xxxx} + (r~\psi_x)_x$,
where $\psi=\psi(x)$ and $r=r(x)$. Periodic boundary condition is employed. It claims that the operator $...
- 227
0
votes
0
answers
92
views
How to estimate stability and stiffness of a system of coupled ODEs?
I'm running into issues with Python/Julia ODE solvers requiring prohibitively small timesteps to evolve a system of 4 coupled ODEs (the order of magnitude of the state variables and time unit span ~40-...
- 193
5
votes
1
answer
118
views
Largest singular value without using the adjoint
The square of the largest singular value of a linear map $A$ can be computed by using the power iteration for $A^TA$ and one advantage of this is that the iteration is matrix free, i.e. you only need ...
- 1,738
1
vote
2
answers
295
views
Calculate average distance between pairs of points without computing full distance matrix
Suppose I have a set of $N$ points of shape $N \times D$, where $D$ is the dimensionality. I want to compute the average Euclidean distance between all points, as well as additional moments such as ...
- 165
2
votes
1
answer
109
views
Finding the correct order of eigenvectors of a parameter-dependent Hermitian matrix
so, I have a symmetric, analytic matrix $\mathbf{H}(x)$ ($x$ is real). Because $\mathbf{H}(x)$ is analytic and $x$ is real, it is possible to find analytic functions for the eigenvectors and the ...
- 153
-1
votes
1
answer
44
views
Finding matrix of a linear transformation using R programing
The full question is:
Let {u1, u2,···, un} and {x1, x2,···, xm} be bases for Rn and Rm respectively. Let T:Rn→Rm be the linear transformation whose associated matrix with respect to the above bases is ...
2
votes
1
answer
140
views
Numerical diagonalization of Hamiltonian
Framework
I am trying to diagonalize the Bogoliubov-de Gennes Hamiltonian. The problem is that the Hamiltonian contains a Laplacian. This could be solved by using a discretized Laplacian.
How I tried ...
- 21
3
votes
1
answer
70
views
Requesting for Finite Difference Methods reference in Portuguese or English
Crossposted on Mathematics SE
I have been assigned a group project for an introductory Linear Algebra subject on Finite Difference Methods and sparse matrices. Our professor advised we use Gilbert ...
- 33
2
votes
0
answers
45
views
Solving linear system and obtaining operator norm
I need to solve a linear system of the form $(\mathrm{Id} + \mathbf{J})\mathbf{x} = \mathbf{b}$ for $\mathbf{x}$ and I also need to compute the operator norm of $\mathbf{J}$ (i.e. the largest singular ...
- 183
1
vote
1
answer
100
views
Fast algorithm to compute chi-square
I would like to evaluate the chi-square of the form $\chi^2=v^{T}C^{-1}v$ where $v$ is a column vector and $C$ is a covariance matrix. Both $v$ and $C$ are known and $C$ is a $740\times740$ matrix. ...
- 123
0
votes
0
answers
276
views
Solving huge dense square symmetric linear system
I have a linear system of the type
$A x = y$
where A is a dense, square, symmetric, positive definite matrix, $x$ a vector of unknown parameters, and $y$ is a vector of observed quantity.
I know that ...
- 153