As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [numerical-linear-algebra]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
81 views

Substitution vs elimination in solving system of linear equations [closed]

I believe that elimination is generally the preferred method to solve a system of linear equations compared with substitution. To be precise, by substitution method on a system of linear equations, it ...
muddy's user avatar
  • 31
1 vote
1 answer
48 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
39 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
30 votes
3 answers
2k 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
78 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
47 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
115 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
63 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 ...
Leonardo's user avatar
  • 155
29 votes
2 answers
745 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,511
3 votes
1 answer
96 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
0 votes
0 answers
32 views

The backward error of tridiagonal linear system $Ax=b$ by Gaussian elimination without pivoting

Let $A$ be an $n \times n$ nonsingular tridiagonal matrix having an $LU$ factorization. It can be shown that the computed solution of the linear system $Ax = b$ using Gaussian elimination without ...
Kevin Lin's user avatar
1 vote
0 answers
12 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
30 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
106 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
383 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
0 votes
0 answers
30 views

Testing a condition in linear algebra involving Krylov subspaces

Let $A \in \mathcal{M}_n(\mathbb{R})$ be a real-valued $n \times n$ matrix. For $b \in \mathbb{R}^n$, I consider the Krylov subspace $$K_A(b) = \operatorname{span} \{ b, A b, \dotsc, A^{n-1} b \}.$$ ...
cs89's user avatar
  • 916
1 vote
1 answer
74 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
  • 741
1 vote
1 answer
71 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
  • 741
3 votes
1 answer
177 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,764
1 vote
0 answers
84 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,764
2 votes
1 answer
260 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,764
1 vote
1 answer
85 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,511
3 votes
0 answers
122 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,511
0 votes
0 answers
13 views

How do I know sparse identification of nonlinear dynamics (SINDy) is correct?

Here is the algorithm/technique in question, https://www.youtube.com/watch?v=NxAn0oglMVw. How do I know that this algorithm is correct? No where in any of the papers do they talk about a proof? What ...
Tobias Rieper's user avatar
0 votes
0 answers
85 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
42 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
68 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
0 votes
0 answers
17 views

Identifying redundant vectors In non-negative matrix bases

I have a target non-negative matrix $X$ that I would like to factor. I have two non-negative matrices $W$ and $H$ such that $WH = X$. In this formulation, the rows of $H$ are $L^2$ normalized and ...
dhakim's user avatar
  • 13
1 vote
1 answer
57 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
32 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
113 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
44 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
  • 141
2 votes
0 answers
25 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
198 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
  • 309
2 votes
2 answers
206 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,769
2 votes
0 answers
109 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
5k 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
154 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
110 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
0 votes
1 answer
97 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 ...
sansaqua's user avatar
0 votes
1 answer
107 views

Proving maximum value of a determinant of $I - B$, where $B$ is nonnegative matrix

I have the following setting: Let $0 \leq r < 1$ and let $\{z_i\}_{i=1}^k$ be $k$ complex numbers such that $|z_i| \leq r$ for all $i$. Moreover, $r + \sum_{i=1}^k 2Re(z_i) \geq 0$ I am interested ...
Bee's user avatar
  • 59
3 votes
2 answers
713 views

Iterative methods for linear system with non-diagonally dominant matrix

I have a linear system \begin{align*} \left[\begin{array}{cccc} 1 & 2 & 1 & -1 \\ 3 & 2 & 4 & 4 \\ 4 & 4 & 3 & 4 \\ 2 & 0 &...
mohd's user avatar
  • 65
0 votes
1 answer
140 views

Correct way to conduct equilibrium scaling of linear/integer/MIP program

I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...
asdf's user avatar
  • 21
1 vote
1 answer
183 views

Does Wilkinson's shift need to be discontinuous?

Given a symmetric Hessenberg matrix $A = \left[\begin{matrix}\ddots& \vdots & \vdots\\\dotsb & a & b\\\dotsb& b & c\end{matrix}\right]$, the Wilkinson shift $\mu$ employed in ...
wlad's user avatar
  • 4,511
3 votes
1 answer
130 views

Smooth, non-analytic functions of non-normal matrices

My apologies if this isn't a well-enough-posed question, I think I'm partly unsure of what exact question to even ask. There are many different ways in which we can take a function of a matrix. We ...
Yonah Borns-Weil's user avatar
2 votes
1 answer
248 views

Is it possible to obtain orthogonal (but not normalized) vectors after QR factorization?

After QR decomposition of a matrix, $M$, the columns of Q are orthonormal. Is it possible after obtaining Q, we recover unnormalized column vectors from $Q$? For example, the matrix M has the ...
AChem's user avatar
  • 741
2 votes
0 answers
103 views

Convolution integral and its matrix representation

My background is chemistry and I was exploring some one dimensional deconvolution problems i.e., resolution of two or more overlapping peaks. A lot of excellent work was done in the 1970-80s. However, ...
AChem's user avatar
  • 741
2 votes
1 answer
77 views

Where has the necessary and sufficient condition for the convergence of the unshifted QR algorithm been stated?

I've obtained a necessary and sufficient condition for the unshifted QR algorithm to converge. The condition for the algorithm to converge for a square matrix $M$ is: For any two eigenvalues $\lambda$...
wlad's user avatar
  • 4,511
2 votes
0 answers
153 views

Maximize the product of Hadamard matrix and a vector

Let $X$ be an $n \times n$ Hadamard matrix (i.e. entries are in $\{-1,1\}$ and rows are orthogonal). For my application, we can assume $n=2^k$. Given a vector $\bf{w} \in R^n$, I want to find the $X^*$...
EVAN YANG's user avatar
6 votes
2 answers
978 views

Complexity of rectangular matrix multiplication

I am interested in the complexity of multiplying two matrices $A$ and $B$, i.e. to compute $AB$. From [Le Gall and Urrotia], I know that: if $A$ and $B$ are square-matrices of size $n$, then this can ...
N. Gast's user avatar
  • 552

1
2 3 4 5 6