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,053
questions
9
votes
1
answer
197
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 ...
- 1,442
3
votes
2
answers
735
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 ...
1
vote
0
answers
63
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.
...
- 11
2
votes
0
answers
112
views
Global minimum of a function involving matrix exponentials
I have a matrix system
\begin{equation}
\vec{x}(t) = e^{(iAt)} \vec{x}(0)
\end{equation}
that comes from the solution of the differential system
\begin{equation}
\frac{d}{dt}\vec{x} = iA\vec{x},
\end{...
- 21
2
votes
0
answers
48
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 &...
- 1,442
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 ...
- 956
2
votes
1
answer
140
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 ...
- 818
4
votes
2
answers
116
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)...
- 956
6
votes
1
answer
201
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 ...
- 1,442
3
votes
1
answer
138
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 ...
- 1,442
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^\...
- 173
2
votes
1
answer
114
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,088
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
85
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 ...
- 119
1
vote
1
answer
94
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 $...
- 217
0
votes
0
answers
37
views
Solving Symmetric/Hollow Matrix issue
I have a particular issue and need something creative or solution from calculus.
I have Symmetric/Hollow Matrix, a numbers are % of mismatch between them. Ideally, all of them should be 0, but I have ...
0
votes
0
answers
71
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
101
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,728
1
vote
2
answers
68
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
92
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
39
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
106
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
63
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
0
votes
0
answers
38
views
Matrix 3D rotation/translation/scaling relative to each other
I am trying to implement an algorithm, that removes a part of an assembly (3D) and translates/rotates/scales those other matrices which are child/parent to a new matrix. For example:
(MT = ...
- 101
2
votes
0
answers
43
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
75
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
175
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 ...
- 121
5
votes
1
answer
190
views
Converting distance matrix back into original data
Suppose that we have $N$ points, and a distance matrix $D \in \mathbb{R}^{N \times N}$ describing the Euclidean distance among those points. For now, assume that we do not necessarily know how many ...
- 165
6
votes
1
answer
114
views
Fast way of computing the action of a matrix power on a vector
For integer $k>0$, it is well-known that one can use binary exponentiation to evaluate the matrix power $\mathbf A^k$, where $\mathbf A$ is an $n\times n$ matrix.
However, it is not clear to me if ...
- 61
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 ...
- 293
9
votes
2
answers
246
views
Efficiently estimating trace of a product of matrices
I have $d\times d$ real-valued matrices $A_1,\ldots,A_k$, $1000<d<4000$, $k\approx 50$, and need to estimate the trace of the following matrix product
$$t=\text{tr}(A_1 A_2\cdots A_k A_k^T \...
- 1,442
0
votes
0
answers
85
views
Weighted Jacobi Not Working on 1D Poisson (Issue with Optimal $\omega$)
I've been trying to learn some numerical linear algebra, and I decided to try to implement the weighted Jacobi method to the 1D Poisson problem $$-u''(x)=f(x),\qquad u(0)=a,\ u(1)=b,$$ where we ...
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 ...
2
votes
2
answers
70
views
How to find fundamental matrix based on other fundamental matrix and camera movement?
I am trying to speed up some multi-camera system that relies on calculation of fundamental matrices between each camera pair.
Please notice the following is pseudocode. ...
- 121
0
votes
1
answer
50
views
why is $Hx= x-2u^{H}xu$ ? why not $Hx= x(x-uu^H) + 2((u^Hx)u)^2? $
I have some confusion in this diagram
My confusion : why is $Hx= x-2u^{H}xu$ ? why not $Hx=x(x-uu^H) + 2((u^Hx)u)^2?
$
My thinking is that by using pythogoras theorem blue line(vector) denotes ...
- 101
0
votes
1
answer
123
views
Incomplete Cholesky factorization algorithm
I want to implement incomplete Cholesky factorization to precondition, the algorithm I refer from incomplete Cholesky factorization,
...
- 11
1
vote
0
answers
50
views
Trouble inverting complex matrix with numpy and scipy
I have some matrix-valued, complex data $Z(f)$ with $f\in\{f_0,f_1,\dots\}$ and $Z(f_i)$ being a 3x3 matrix. I require the inverse $Z^{-1}(f)$ in my workflow. After encountering some problems with my ...
- 11
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 ...
- 2,088
10
votes
1
answer
484
views
Generalization of eigendecomposition problem
Let $A\in \mathbb{R}^{n\times n}$ and $v \in \mathbb{R}^n$. We recognize $Av=\lambda v$ for some scalar $\lambda$ as an eigendecomposition problem. Suppose $\mu \in \mathbb{R}^n$, and let $\odot$ ...
- 173
4
votes
1
answer
218
views
Is there any way/any python function to calculate the condition number of the roots of a polynomial directly?
I know that NumPy has linalg.cond(A) to find the condition number of a matrix A. But, if I want to find the condition numbers of the roots of a large polynomial ...
- 41
2
votes
1
answer
115
views
Can someone explain the equivalence between Oja's rule and PCA in a simple way?
I have to give a presentation on unsupervised learning in 2 days, and I have to explain/show the equivalence between Hebb's learning rule (or Oja's rule to be more specific) and PCA. The thing is that ...
2
votes
0
answers
98
views
Regularisation of ill-conditioned matrix-vector problem
I have a linear* problem which arises from an integro-differential system, and writes:
$$
(\mathbf{I}+\lambda \mathbf{A})x = b
$$
where $\mathbf{A}$ is a real full matrix, size $n\times n$, but is not ...
6
votes
1
answer
238
views
PETSc-like library for Julia
I want to build an application for Material Point Method (and probably other meshfree methods too) in Julia and I am looking for library for direct and iterative solvers that can help me with it. One ...
- 63
5
votes
2
answers
484
views
Computational method to compute both the (log) determinant and inverse of a matrix
Suppose I have a square matrix $\mathbf{A} \in \mathbb{R}^{n\times n}$ and a vector $\mathbf{b}\in\mathbb{R}^n$. In my application I need to accomplish two things.
I need to find the solution of the ...
- 183
4
votes
1
answer
109
views
Solving for a single element of a solution of a linear system
I wish to solve a linear system $A x =b$ in which $A$ is dense but not too large, say no larger than $10\times10$. However, I am not interested in the full solution vector $x = [x_0, x_1, \dots]$, ...
- 695
2
votes
0
answers
67
views
Multigrid method: linear solver and modified residual
I am trying to better understand the FAS multigrid algorithm for Euler equation in FV discretization. The usage of the modified residual (the residual with forcing) inside the different cases:
...
- 382
3
votes
1
answer
89
views
Find $x$ that satisfy $(I-A^*A)+x(\frac{A+A^*}{2})\prec0$ using LMI or SDP on Matlab
Given $A\in\mathbb{C}^{n\times n}$, I want to use LMI or SDP to find feasibility of $x>0$ in the following inequality:
$$(I-A^*A)+x(\frac{A+A^*}{2})\prec0,$$
where $D\prec0$ means that $D$ is ...
- 183
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}$. $\...
- 141
0
votes
2
answers
127
views
Implementation of $[X, \cdot]$ as an $n^2 \times n^2$ matrix, where $X$ is an $n \times n$ matrix
Let $M_n(\mathbb{R})$ denote the set of $n\times n$ matrices with real entries. I have an $n\times n$ matrix $X\in M_n(\mathbb{R})$, and I would like to implement the linear operator $[X, \cdot] : M_n(...
- 185
5
votes
2
answers
117
views
Optimizing a quadratic form integral over unit sphere
I have an optimization problem, which is to maximize the following integral over the unit sphere:
$$
\max_B \int d\Omega \mathbf{f}^{\dagger}(\theta,\phi) (B^{\dagger} + B) \mathbf{f}(\theta,\phi)
$$
...
- 51