Questions tagged [numerical-linear-algebra]
{numerical-linear-algebra} questions involving algorithms for linear algebra computations.
289
questions
2
votes
1
answer
229
views
How to solve this set of equations as efficiently as possible (with "efficiently" measured in FLOPS)?
The system of equations is the following:
$$
\Gamma_i^{\ -1} = \sum_{i=1}^nA_{ij}\Gamma_j,
$$
where $\Gamma = (\Gamma_i)$ is a vector of size $n$ and $A$ is a matrix of size $n\times n$, with $n \gt ...
0
votes
0
answers
47
views
Concentration of bilinear forms
This is a bit vague so I'll begin by indicating the motivation. I am looking for ways to [do something interesting or useful] with the self-attention in transformer models. Ultimately the self-...
1
vote
0
answers
42
views
Computing smallest singular value of a matrix with explicit error control?
Many good algorithms are out there computing truncated SVD: What is the time complexity of truncated SVD?.
I am trying to implement some codes to find the smallest singular value of a big matrix $A$. ...
0
votes
1
answer
68
views
Matrix quantization and effect on singular values
Let $A$ and $B$ be an $N\times n$ matrix with $n\le N$, and let $\sigma_1(X),\dots \sigma_n(X)$ denote the singular values of $X\in \{A,B\}$. Do we have upper and lower bounds for
$$
\|
\sigma_i(A)-\...
0
votes
0
answers
25
views
The selection of minimal generating sets in Lie algebra
Suppose $A$ is a Lie algebra on field $F_{p}$ with $[A,A,A]=0$. Denote $\{a_{1},\cdots,a_{d}\}$ is a minimal generating set of $A$.It's possible that $[a_{i},a_{j}]=0$ for some $1\leq i<j\leq d$ ...
2
votes
1
answer
233
views
Computing 3-term connection coefficients for wavelets
I am trying to calculate the three-term connection coefficients
$$
Λ_{l,m}^{d_1,d_2,d_3} = \int_{-\infty}^\infty \varphi^{(d_1)}(x) \varphi^{(d_2)}_l(x) \varphi^{(d_3)}_m(x) dx
$$
for Daubechies ...
0
votes
1
answer
234
views
What is the best way to choose initial basis when applying simplex method to an equality form of LP?
Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...
6
votes
1
answer
175
views
Efficiently solve the Sylvester equation $AX+XA = C$ where $X$ is skew-symmetric
Is there a way (more efficient than the standard vectorization) to solve the following Sylvester equation in the skew-symmetric matrix $X$ $$AX+XA = C$$ where the matrix $A$ is symmetric positive ...
1
vote
1
answer
271
views
Best approximation with tensors of rank $\ge2$
Let $k\in\mathbb N$, $H_i$ be a (finite-dimensional, if necessary) $\mathbb R$-Hilbert space for $i\in I:=\{1,\ldots,k\}$, $H:=\bigotimes_{i\in I}H_i$ denote the tensor product$^1$ of $(H_i)_{i\in I}$ ...
1
vote
0
answers
174
views
Connection of eigenspace of finite Hilbert matrix and its continuous operator counterpart
I am trying to understand the connection between the eigenspace of the continuous operator
$$
H(x,y) = \frac{1}{x+y}
$$
which is nothing but the square of the Laplace operator, and its discrete ...
2
votes
1
answer
97
views
Cosine-sine decomposition yields zero diagonals
I have implemented the Cosine-Sine decomposition of a square matrix in Mathematica. That is, for a given matrix $U$ (where in my use-case, $U$ is unitary) with equally-sized partitions
$$
U = \begin{...
4
votes
2
answers
626
views
Difference between Chebyshev first and second degree iterative methods
Consider linear equation $Au = f$.
We want to solve it with iterative method (assuming $A$ is good).
First order iterative method is:
$$
u^{k+1} = u^k - \alpha_{k+1}(Au^k - f),
$$
The second degree ...
1
vote
0
answers
314
views
The geometrical multiplicity of the nilpotent matrices
The following point is well-known in the literature.
Theorem. Let $A$ be a non-negative matrix in $M_n(\mathbb{R})$. If $A$ is nil-potent, there is a permutation matrix $P$ such that $P^tAP$ is ...
2
votes
2
answers
166
views
Theoretical/Practical Implications of DFT Eigenvectors
Discrete Fourier transform (DFT) has only four distinct eigenvalues: $±1$ and $±i$. For large matrices , each eigenvalue $λ$ yields a multidimensional eigenspace, allowing linear combinations of ...
3
votes
1
answer
175
views
Inflection point calculation for cubic Bézier curve encounters division by zero
I've been working on finding the inflection points of a cubic Bezier curve using the method described in a paper Hain, Venkat, Racherla, and Langan - Fast, Precise Flattening of Cubic Bézier Segment ...
2
votes
1
answer
135
views
How to do LU factorization efficiently based on the factorized result added with a low-rank matrix?
Suppose a square $n\times n$, dense matrix $A^{\text{old}}$ has been factorized into $L^{\text{old}}$ and $U^{\text{old}}$ components by performing a LU decomposition $A^{\text{old}} = L^{\text{old}}U^...
0
votes
2
answers
117
views
Reshaping data vector into a matrix for deconvolution using a circulant matrix
Suppose we have a circulant matrix S made from pseudorandom binary sequence of length $N$ consisting of $0$'s or/and $1$'s. $1$ means that we can inject something for chemical analysis and $0$ means ...
0
votes
0
answers
23
views
How can one orthogonalize the pointwise sum of two orthogonal sets?
Let $n = 2k$, and suppose that $V = \{v_1, \cdots, v_k\}$ is an orthogonal set in $\mathbb{R}^n$. In other words, the vectors in set $V$ are pairwise orthogonal to each other.
Now, consider a new set $...
5
votes
0
answers
196
views
Difficulty of solving $Ax=b$ in terms of limiting spectral density of $A$?
Suppose $A$ is a random real-valued $n\times n$ matrix and we want to know the difficulty of solving $Ax=b$ when entries of $b$ are sampled IID from Normal$(0,1)$.
Can we say anything about the ...
0
votes
0
answers
85
views
Efficient method to determine minimum eigenvalue of $2 \times 2$ block diagonal matrix
Suppose $H$ is a $2 \times 2$ block-diagonal symmetric matrix in $\mathbb{R}^{2^N \times 2^N} $. That is
$$ H = \begin{pmatrix} A_1 & 0 & \cdots & 0\\ 0 & A_2 & \cdots & 0 \\
...
1
vote
0
answers
57
views
Backward stability of the SVD
I am interested in the backward stability of numerical algorithms for computation of the singular value decomposition (SVD). Specifically, I am interested in the following result:
Backward stabile ...
1
vote
1
answer
58
views
Characterization of the behavior of the residuals in conjugate gradient
In conjugate gradient method for solving symmetric positive definite linear system $Ax=b$, which can also be regarded as a convex optimization problem $\dfrac{1}{2} x'Ax - x'b$, the $A$-norm of the ...
34
votes
3
answers
3k
views
Quickly determining if a matrix has any PSD completion
Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?
Slightly more precisely: for simplicity let's assume ...
20
votes
2
answers
17k
views
Complexity of linear solvers vs matrix inversion
Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given ...
0
votes
2
answers
301
views
Solving sparse linear least squares or a positive definite 5-band matrix system fast
I want to quickly solve the following linear least-squares problem
$$\min_{x \in \mathbb{R}^n} \left\| A x - b \right\|_2^2$$
with a special sparse structure where each row in $A$ has only up to $4$ ...
7
votes
2
answers
8k
views
Conditions for convergence of Euler's method
It is known that a sufficient and necessary condition for
$$\dot y(t) = f(y(t), t), \quad t > 0, \quad y(0) = y_0$$
to have a unique solution is $f$ Lipschitz in $y$ and continuous in $t$. However, ...
11
votes
3
answers
8k
views
Eigenvectors of a symmetric positive definite Toeplitz matrix
I wish to efficiently compute the eigenvectors of an n x n symmetric positive definite Toeplitz matrix K. A full eigendecomposition would be even better.
Although I assumed this would be a well ...
1
vote
0
answers
124
views
QR algorithm for eigenvalues and eigenvectors of large symmetric matrices
I am trying to write a QR algorithm in Python for eigenvectors and eigenvalues finding for large symmetric matrices,
My initial thought was to use Householder transformation with a Wilkinson shift ...
1
vote
1
answer
107
views
Can the condition number of a Jordan basis be made stubbornly large?
For each $k \in \mathbb R$, does there exist a non-empty open ball $B$ of $\mathbb R^{2 \times 2}$ such that for all $M \in B$ and Jordan decompositions $PJP^{-1}$ of $M$, the condition number $\kappa(...
3
votes
0
answers
210
views
Efficient way to calculate Smith Normal Form of large integer matrices
I am interested in calculating the Smith Normal Form for Laplacian matrices of hypercube graphs. Using the elementary divisors method from SAGE, I was able calculate up to the 11-cube (which has a $2^{...
1
vote
0
answers
99
views
Generalized eigenvalues of block matrix
Let $A, D \in \mathbb{R}^{n\times n}$ be symmetric matrices and consider the following matrix pencil
$$
\begin{pmatrix}
-I & A+\lambda I \\
A+\lambda I & -D \\
\end{pmatrix}
$$
If we already ...
3
votes
0
answers
206
views
efficient numerical algorithm for matrix determinant
It appears that in numerical analysis the question of computing the determinant $\det A$ of a real or a complex $n\times n$ matrix $A$ is not well-studied, and a usual recommendation is to use matrix ...
29
votes
2
answers
1k
views
Gaussian elimination is just Gram-Schmidt with a change to the inner product symbol?
I noticed at some point that if you take the Gram-Schmidt algorithm for taking the QR decomposition of a matrix, and you change the meaning of the inner product symbol $\langle \mathbf u, \mathbf v \...
2
votes
1
answer
213
views
Linear system with sum of Kronecker products
Here and here, specific ways to address the equation in $x$, for $N=2$, are given:
$$\sum_{i=1}^N (A_i\otimes B_i)x=c$$
Is anything know about the case $N>2$?
I am looking in fact for an efficient ...
3
votes
1
answer
218
views
Complexity of inverting and multiplying against a symmetric Toeplitz matrix with two repeated entries
I know that the computational complexity of inverting a general $n \times n$ matrix $A$ is $O(n^{2.373})$ and multiplying it against an $n \times m$ matrix is $O(n^2m)$. Moreover, I've seen that ...
37
votes
10
answers
18k
views
Fast matrix multiplication
Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in $...
11
votes
1
answer
2k
views
Quantifying the failure of the Cholesky factorization test for indefinite matrices
The Cholesky factorization is the classic test to check if a matrix is positive definite. In infinite precision it is also an exact test: A matrix has a Cholesky factorization iff it is positive ...
1
vote
0
answers
18
views
Optimal Truncation of LDL-factorization to improve conditioning
Suppose I factored real symmetric quasi-definite $ A_0= L_0 \cdot D_0 \cdot L_0^T$ and the factorization exists, with $D$ diagonal and $L$ unit lower-triangular; and suppose $L$ and $D$ are badly ...
1
vote
0
answers
33
views
Slope assertion in Cholesky on digital computers
For a real symmetric positive definite linear system
$$ A \cdot x = b, $$
solved using Choelsky with forward- and backward-substitution, we know it for the numerical approximation $\tilde{x}$ to $x$ ...
3
votes
2
answers
190
views
Practical symmetric equivalent to QR factorization updates
As we know, the QR-factorization $Q\cdot R=A$ of any real symmetric $n \times n$ matrix $A$ with full rank is unconditionally numerically stable. Further, when A is rank-1-updated, the factorization ...
1
vote
1
answer
53
views
Does norm of discrepancy decrease monotonously in CGLS/CGNR
I am the author of the package for tomographic reconstruction https://github.com/kulvait/KCT_cbct I have implemented CGLS/CGNR , algorithm which applies conjugate gradients on normal equation
$$
A^\...
6
votes
2
answers
420
views
Spectrum of operator involving ladder operators
The ladder operator in quantum mechanics are the operators
$$a^\dagger \ = \ \frac{1}{\sqrt{2}} \left(-\frac{d}{dq} + q\right)$$
and
$$a \ \ = \ \frac{1}{\sqrt{2}} \left(\ \ \ \!\frac{d}{dq} + q\...
1
vote
1
answer
213
views
Eigenvalues of a circulant: DFT or Inverse DFT Convention?
Currently, most engineering texts (and webpages including Wikipedia) define forward discrete Fourier transform with a negative sign on the exponential. This is a convention and the inverse discrete ...
1
vote
1
answer
302
views
Extracting eigenvalues of a circulant matrix using discrete Fourier matrix
The eigenvalues of a circulant matrix $C$ can be extracted as $$
\Lambda=F^{-1} C F
$$
where the $F$ matrix is a discrete Fourier transform matrix and $\Lambda$ is a diagonal matrix of eigenvalues.
...
7
votes
2
answers
231
views
Finding $\theta$ such that at least one eigenvalue of $A(\theta)$ is real
Is there a known method to find a set of $\theta$ such that at least one eigenvalue of $A(\theta)$ is purely real?
Assume $A(\theta)$ is a real square matrix whose elements are linear functions of a ...
3
votes
1
answer
179
views
The proof of the invertibility of $\Big( \sin\frac{8kl\pi}{2n+1} \Big)_{k,l=1}^\frac{n}{2}$
Suppose that $n$ is even. Any suggestion/appraoch to prove that $S=\Big( \sin\frac{8kl\pi}{2n+1} \Big)_{k,l=1}^\frac{n}{2}$ is invertible?
2
votes
1
answer
294
views
The eigenvalues of the matrix $\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$
What are the eigenvalues/eigenvectors of the matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$ when $n$ is odd?
1
vote
0
answers
127
views
What are the eigenvalues/eigenvectors of the matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^{\frac{n-1}{2}}$ when $n$ is odd?
Suppose that $n$ is odd. The eigen values/eigenvectors of the skew-circulant matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$ are successfully computed in this post.
Q. What are ...
3
votes
0
answers
140
views
Can the Jordan decomposition of a matrix be computed in a backwards stable way?
Let $PJP^{-1}$ denote the Jordan decomposition of $M$. The matrix $J$ is a direct sum of Jordan blocks; it is unique up to permutation of the Jordan blocks. The matrix $P$ is not unique.
There are two ...
34
votes
3
answers
5k
views
Why is uncomputability of the spectral decomposition not a problem?
Below, we compute with exact real numbers using a realistic / conservative model of computability like Type Two Effectivity.
Assume that there is an algorithm that, given a symmetric real matrix $M$, ...