Questions tagged [numerical-linear-algebra]

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

Filter by
Sorted by
Tagged with
52 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}$). ...
Vidit Nanda's user avatar
  • 15.4k
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 $...
ilyaraz's user avatar
  • 1,771
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$, ...
wlad's user avatar
  • 4,823
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
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$? ...
alext87's user avatar
  • 3,167
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\\ && \...
Alec Jacobson's user avatar
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 ...
Lepidopterist's user avatar
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 ...
lino's user avatar
  • 253
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 ...
Alec Jacobson's user avatar
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 ...
messcode's user avatar
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-...
Jeff's user avatar
  • 500
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 ...
Federico Poloni's user avatar
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 ...
Federico Poloni's user avatar
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\...
Jiro's user avatar
  • 909
5 votes
3 answers
669 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{\...
sb945's user avatar
  • 153
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 $...
Saheb's user avatar
  • 21
2 votes
1 answer
489 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 ...
lisi's user avatar
  • 101
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 ...
ABB's user avatar
  • 3,898
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?
ABB's user avatar
  • 3,898
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 "...
Alejandro Alvarez-Socorro's user avatar
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,823
1 vote
1 answer
280 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{...
fusiled's user avatar
  • 39