Questions tagged [numerical-linear-algebra]

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

Filter by
Sorted by
Tagged with
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-...
Felix Goldberg's user avatar
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$. ...
Ma Joad's user avatar
  • 1,591
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)-\...
ABIM's user avatar
  • 4,989
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$ ...
gdre's user avatar
  • 71
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 ...
Gabi's user avatar
  • 163
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 ...
knuth's user avatar
  • 29
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{...
Anti Earth's user avatar
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 ...
ABB's user avatar
  • 3,898
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 ...
Ziamor's user avatar
  • 133
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^...
Alex Joe's user avatar
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 $...
ABB's user avatar
  • 3,898
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 ...
AChem's user avatar
  • 803
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 ...
Yaroslav Bulatov's user avatar
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 \\ ...
KAJ226's user avatar
  • 131
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 ...
eepperly16's user avatar
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 ...
ABB's user avatar
  • 3,898
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 ...
bernard's user avatar
  • 205
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 ...
Daniel Belaish's user avatar
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 ...
Paul Christiano's user avatar
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^{...
presidentediniente's user avatar
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 ...
bernard's user avatar
  • 205
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 ...
Dima Pasechnik's user avatar
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 ...
Lilla's user avatar
  • 225
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 \...
wlad's user avatar
  • 4,792
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 ...
Annie's user avatar
  • 71
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 ...
kaisong's user avatar
  • 51
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$ ...
kaisong's user avatar
  • 51
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 ...
kaisong's user avatar
  • 51
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\...
António Borges Santos's user avatar
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 ...
AChem's user avatar
  • 803
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. ...
AChem's user avatar
  • 803
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?
ABB's user avatar
  • 3,898
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 ...
ABB's user avatar
  • 3,898
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?
ABB's user avatar
  • 3,898
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(...
wlad's user avatar
  • 4,792
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 ...
wlad's user avatar
  • 4,792
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 $...
Nxy's user avatar
  • 1
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 & \...
matthewd49's user avatar
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 ...
dhakim's user avatar
  • 13
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},\...
Vladimir Zolotov's user avatar
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 ...
Scezory's user avatar
  • 11
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 ...
Yaroslav Bulatov's user avatar
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^\...
VojtaK's user avatar
  • 151
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*}...
Bjornson's user avatar
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 ...
CWC's user avatar
  • 351
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\...
Andi Bauer's user avatar
  • 2,901
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 ...
user1067171's user avatar
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 ...
Jiawei Ren's user avatar
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 ...
L.A. Reba's user avatar
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$. ...
AspiringMat's user avatar

1
2 3 4 5 6