Questions tagged [numerical-linear-algebra]

{numerical-linear-algebra} questions involving algorithms for linear algebra computations.

Filter by
Sorted by
Tagged with
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$, ...

1
2 3 4 5 6