All Questions
Tagged with matrices numerical-linear-algebra
15 questions
58
votes
2
answers
18k
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}$). ...
- 15.5k
38
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 $...
- 1,791
34
votes
3
answers
6k
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$, ...
- 4,943
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 ...
- 777
16
votes
2
answers
4k
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$?
...
- 3,217
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 ...
- 947
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 ...
- 83
7
votes
1
answer
305
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 ...
- 173
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 ...
- 20.2k
7
votes
1
answer
246
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 ...
- 20.2k
5
votes
3
answers
693
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{\...
- 153
5
votes
1
answer
260
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\...
- 909
2
votes
1
answer
556
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 ...
- 101
2
votes
1
answer
134
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 $...
- 21
1
vote
1
answer
321
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{...
- 139