Questions tagged [numerical-linear-algebra]
{numerical-linear-algebra} questions involving algorithms for linear algebra computations.
289
questions
0
votes
0
answers
43
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
41
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
67
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$ ...
6
votes
1
answer
171
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
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{...
2
votes
2
answers
159
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
172
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
130
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
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 $...
0
votes
2
answers
115
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 ...
5
votes
0
answers
195
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
83
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
0
answers
313
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 ...
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 ...
1
vote
0
answers
122
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 ...
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 ...
3
votes
0
answers
208
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
98
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
201
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 ...
2
votes
1
answer
204
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 ...
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 \...
3
votes
1
answer
214
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 ...
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
184
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 ...
6
votes
2
answers
418
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
291
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.
...
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?
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 ...
2
votes
1
answer
292
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
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
138
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 ...
0
votes
0
answers
149
views
How to analyse the range of eigenvalues of a symmetric and indefinite matrix?
Let $G$ be a symmetric and indefinite matrix defined as follows
$$ G := S - \begin{pmatrix} I_n & I_n \\ I_n & I_n \end{pmatrix},$$
where $S$ is a symmetric positive definite matrix of size $...
1
vote
0
answers
84
views
Solving a block tridiagonal system with diagonal perturbations
Say we have a block tridiagonal matrix, $T \in \mathbb{R}^{NL \times NL}$, with constant off diagonals, $\mathbf{B} \in \mathbb{R}^{L\times L}$, given by
$$
T = \begin{bmatrix} \mathbf{A}_1 & \...
0
votes
1
answer
72
views
$\det(HH’) = 0$ for nonnegative $H$
$H$ is an $n\times m$ matrix with non-negative coefficients and $n < m$. $H'$ is the transpose of $H$.
Are the following statements true?
If $\det(HH’) > 0$, the rows of $H$ define the edges of ...
1
vote
1
answer
63
views
Given a set of vectors how to pick $M$ such that sum of maximums of coordinates is maximized?
I asked the same on math.Stackexchange.
I have $n$ (say $n = 300$) vectors $v_1,\dots,v_n$. Each of them has $K$ coordinates (say $K = 30$). For vector $v_j$ I denote it's coordinates as $v_{j1},\...
1
vote
0
answers
35
views
Efficient solution to linear matrix equations
A general form for a linear matrix equation can be written as
$$AX + XB + \sum C_iXD_i$$
If $C_i$ and $D_i$ are all 0, then this simplifies into a well known and studied matrix equation that has an ...
3
votes
0
answers
116
views
Preconditioners for $Ax=y$ that rely on hierarchical statistical modeling
Solving $Ax=y$ exactly can be done as:
fit a linear autoregressive model by treating rows of $A$ as data
apply this model to $A^T y$
Imperfect predictive model corresponds to an approximate inverse ...
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^\...
2
votes
0
answers
26
views
Solve sparse system with nested inverse
What is the most efficient way to solve an equation
\begin{align*}
(A\,E^{-1}\,C) x = b, \qquad A\in \mathbb{R}^{m\times n}, \, E \in \mathbb{R}^{n\times n}, \, C\in \mathbb{R}^{n\times m}
\end{align*}...
7
votes
2
answers
230
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 ...
2
votes
2
answers
219
views
Sum over exponentiated bilinear form in finite-field vector space
Let $A$ be a linear map over the finite-field vector space $(\mathbb F_2)^n$, i.e., an $\mathbb F_2$-valued $n\times n$ matrix, not necessarily symmetric. I'm interested in the sum
$$Z(A) = \sum_{X\...
2
votes
0
answers
117
views
Proving some properties of the Landweber–Fridman iterates
$\newcommand\norm[1]{\lVert#1\rVert}$Let $B\in \mathbb R^{n\times n}$ be a symmetric and positive definite matrix. Assume that $x\in \mathbb R^n$ is the solution of $Bx=w$ for some given $w\in \mathbb ...
17
votes
4
answers
6k
views
Why is fast matrix multiplication impractical?
I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication.
I read some content saying fast matrix multiplications are impractical because of large ...
1
vote
0
answers
214
views
Find the eigenvectors from the QR algorithm in the unsymmetric case
It is possible to find many references describing the QR Algorithm with more or less refinements to approximate the eigenvalues of a square matrix $A\in\mathbb{R}^{n\times n}$.
I implemented a version ...
1
vote
0
answers
179
views
Complexity of singular value decomposition using matrix multiplication oracles
Suppose I have an $n\times m$ real matrix $A$, $n\ll m$ with full row rank $(\mathrm{rank}(A) = n)$. I have an oracle that can compute $Ax$ or $A^T y$ for any $x\in \mathbb{R}^m, y\in \mathbb{R}^n$. ...