Questions tagged [numerical-linear-algebra]
{numerical-linear-algebra} questions involving algorithms for linear algebra computations.
22
questions
57
votes
2
answers
17k
views
How fast can we *really* multiply matrices?
Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.807})$ for the multiplication of two $n \times n$ matrices (the exponent is $\frac{\log7}{\log2}$). ...
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 $...
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 ...
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$, ...
16
votes
2
answers
3k
views
The singular values of the Hilbert matrix
The $n\times n$ Hilbert matrix $H$ is defined as follows
$$H_{ij} = \frac{1}{i+j-1}, \qquad 1\leq i,j\leq n$$
What is known about the singular values $\sigma_1 \geq \cdots \geq \sigma_n$ of $H$?
...
15
votes
2
answers
7k
views
Efficient rank-two updates of an eigenvalue decomposition (or more generally SVD)
Let $A$ be a symmetric matrix with eigenvalue decomposition $UDU^T$. Golub, et al.1 and Bunch, et al.2 have shown that given such an $A$, the eigenvalue decomposition of $A+\rho xx^t$ may be computed ...
15
votes
2
answers
6k
views
Linearly constrained eigenvalue problem
Suppose I'd like to:
\begin{align}
\mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\
\text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\
&& \...
12
votes
2
answers
4k
views
Why Householder reflection is better than Givens rotation in dense linear algebra?
It’s obvious that Givens rotation works better with sparse matrices. But I don’t know why Householder reflection is better for dense matrices. Does it require less computations? Or it’s numerically ...
11
votes
2
answers
4k
views
How can one construct a sparse null space basis using recursive LU decomposition?
Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
8
votes
1
answer
1k
views
Square root of a large sparse symmetric positive definite matrix
I am trying to calculate
$$Y = A^{\frac 12} X$$
where $A$ is a very large and sparse positive definite matrix, say, $10^4 \times 10^4$. Matrix $X$ is known and, say, $10^4 \times 100$. Is there any ...
8
votes
1
answer
1k
views
Efficiently compute the trace of a sparse matrix times the inverse of a sparse matrix?
How can I efficiently compute
$\mathrm{trace}(A(B^{-1}))$
where $A$ and $B$ are both sparse symmetric PSD $n \times n$ matrices, both with $O(n)$ non-zero entries? If it helps, the pattern of non-...
7
votes
2
answers
3k
views
Factorizing a block symmetric matrix
Let $X,Y\in\mathbb{R}^{n\times n}$ be symmetric matrices. You may assume that $X$ is positive semidefinite and $Y$ negative semidefinite, if needed, but not that they are invertible.
I would like to ...
7
votes
1
answer
231
views
Add a multiple of $I$ to a matrix to minimize its operator norm
Given $A\in\mathbb{C}^{n\times n}$, what is $s_* = \arg\min \|A-sI\|$?
Here $\|A\|$ is the operator norm, $\|A\|=\rho(A^*A)^{1/2}$, and $I$ is the identity.
The corresponding problem for the ...
5
votes
3
answers
671
views
Norm of triangular truncation operator on rank deficient matrices
Let $T_{n\times n}$ be a triangular truncation matrix, i.e.
$$T_{i,j}=\begin{cases}1 & i\ge j\\ 0 & i<j \end{cases}$$
It is known that for arbitrary $A_{n\times n}$
$$\|T\circ A\|\le\frac{\...
5
votes
1
answer
246
views
Numerical minimization spectral norm under diagonal similarity
This question is a follow up.
Let $A$ be a real square matrix of size $n \times n$. How to determine the minimum spectral norm under diagonal similarity, i.e.,
$$
s(A) = \inf_{D} \lVert D^{-1} A D\...
2
votes
2
answers
177
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 ...
2
votes
1
answer
297
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?
2
votes
1
answer
2k
views
Eigenvalue and Eigenmatrix of a 3D Tensor - How to calculate it?
How to calculate easily the eigenmatrix of a 3D tensor.
I try immersing the tensor in a big matrix, in my case, the tensor is of nxnxn and I can build an n^2 x n^2 matrix that contains all the "...
2
votes
1
answer
133
views
Quadratic matrix equation for $X\in \mathbb{C}^{ n\times p}$ with Hermitian parameters
Let $A\in \mathbb{C}^{ n\times n}$ and $B \in \mathbb{C}^{p \times p}$ be Hermitian matrices with $p < n$.
Find matrix $X$ such that $X^*AX=B.$
Solution in the case of positive definite $A$ and $...
2
votes
1
answer
493
views
How to solve a quadratic matrix equation with positive semidefinite constraint?
I have the following quadratic matrix equation:
$$ XAX+X = B $$
where both $A$ and $B$ are given positive definite matrices, and $X$ is a covariance matrix and, hence, positive definite.
When there is ...
1
vote
1
answer
110
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(...
1
vote
1
answer
287
views
Solve linear system with bordered positive definite matrix
I want to solve the usual $A x = b$ system. In block form:
$$ \begin{bmatrix} B & c \\ c^{T} & 0 \end{bmatrix} \begin{bmatrix} x' \\ x_{n+1} \end{bmatrix} = \begin{bmatrix} b' \\ b_{n+1} \end{...