78 votes
Accepted

Why is uncomputability of the spectral decomposition not a problem?

The singular value decomposition, when applied to a real symmetric matrix $A = \sum_i \lambda_i(A) u_i(A) u_i(A)^T$, computes a stable mathematical object (spectral measure $\mu_A = \sum_i \delta_{\...
Terry Tao's user avatar
  • 108k
34 votes

How fast can we *really* multiply matrices?

Recently there is a PhD thesis about the practical fast matrix multiplication algorithms like Strassen: Matrix multiplication is a core building block for numerous scientific computing and, more ...
Jianyu Huang's user avatar
23 votes

Why is uncomputability of the spectral decomposition not a problem?

The SVD decomposition falls under the family of phenomena where discontinuity implies non-computability. (Intuitively, this is because, at the point of discontinuity, infinite precision is required.) ...
Andrej Bauer's user avatar
  • 47.7k
22 votes

Why is uncomputability of the spectral decomposition not a problem?

This is primarily an issue of backwards vs. forwards stability. Good SVD algorithms are backwards stable in the sense that the computed singular values and singular vectors are the true singular ...
Nick Alger's user avatar
  • 1,140
20 votes

Why is fast matrix multiplication impractical?

Matrix multiplication based on Strassen's algorithm is in $O(n^{\log(7)/\log(2)})$ and is quite practical. As far as I am aware, for any exponent $\omega<\log(7)/\log(2)$ the corresponding ...
Henri Cohen's user avatar
  • 11.5k
19 votes

Why is fast matrix multiplication impractical?

I acknowledge that the question concerns Boolean matrix multiplication. However, a good deal of the opposition to fast matrix multiplication algorithms is due to stability issues that can arise when ...
Carl Christian's user avatar
16 votes

Methods of solving linear system of equations, how to select the appropriate method

Disclaimer 1: Treating these topics properly would require a quick course in numerical analysis. Disclaimer 2: If you are using any sane computer system, it's already going to have a library function ...
Federico Poloni's user avatar
13 votes

What is the time complexity of the matrix exponential?

The exponential of a matrix is not, in general, computable explicitly. Strictly speaking, the Complexity of Matrix Exponential does not exist. Instead, you have an approximate calculation and you are ...
Denis Serre's user avatar
  • 51.5k
12 votes
Accepted

What is the time complexity of the matrix exponential?

Moler's paper "Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later" contains the following extracts: In estimating the time required by matrix computations it is ...
Steve Huntsman's user avatar
10 votes

Decide if a matrix is transposable

There are polynomial-time reductions from your problem to Graph Isomorphism and vice-versa. As a quick definition, when I speak of 'subdividing' an edge, I mean to replace each edge $u, v$ with a ...
Adam P. Goucher's user avatar
9 votes
Accepted

The singular values of the Hilbert matrix

I came back to this a few months ago and I can now answer my own question. I hope it is appropriate to answer my own question given the length of time. Bernhard Beckermann and I just submitted a ...
alext87's user avatar
  • 3,167
9 votes
Accepted

Linear equations with absolute values

The problem is NP-hard over any field not of characteristic 2. We show this by reduction from an NP-complete NAE-3-SAT problem of checking satisfiability of a boolean formula $\land_{i} \mathrm{NAE}(...
Mikhail Tikhomirov's user avatar
9 votes
Accepted

Minimize spectral radius with orthogonal matrix

For an $n\times n$ matrix, the answer is $$|\det A|^{\frac1n}.$$ Explanation: on the one hand, $\rho(UA)\ge|\det (UA)|^{\frac1n}=|\det A|^{\frac1n}$. On the other hand, singular value decomposition ...
Denis Serre's user avatar
  • 51.5k
8 votes

Solving a system of linear equations over the integers

To make sure I understand: you have an $m \times n$ matrix and vector in $\mathbb{Z}^n.$ Is the system a priori over- or under-determined? The former case is a little easier than the latter, but in ...
Igor Rivin's user avatar
  • 95.5k
8 votes
Accepted

Complexity of rectangular matrix multiplication

Assuming that efficient means better than the naive $O(n^{2+k})$ multiplication, let us review some possibilities. Padding. For $k > \omega-2$, just pad $A$ with $n-n^k$ zero or garbage rows, ...
Jukka Kohonen's user avatar
7 votes

Is this inequality involving the Frobenius norm right?

For a short fat matrix $G$ (more columns than rows), $\|AG\|_F \geq \sigma_{\min}(G)\|A\|_F \geq n \sigma_{\min}(G) \|A\|$, where $\sigma_{\min}(G)$ is the least singular value of $G$. This follows ...
Federico Poloni's user avatar
7 votes

Is it faster to compute eigenvalues or coefficients of characteristic polynomials?

With the traditional algorithms and complexity measures used in numerical linear algebra (dense real matrices, floating point computations, flop count as a complexity measure), they are both more or ...
Federico Poloni's user avatar
7 votes

Why is fast matrix multiplication impractical?

Addressing the Boolean part. Usually, fast matrix multiplication relies heavily on the element type being a ring; in particular, that every element has an additive inverse. For example, Strassen's ...
Jukka Kohonen's user avatar
7 votes
Accepted

The eigenvalues of the matrix $\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$

Here, we verify the observation of @BrendanMcKay that the eigenvalues are $n$ with multiplicity $(n+1)/2$ and $-n$ with multiplicity $(n-1)/2$. Note that your matrix is skew-circulant, and it is known ...
Jason Gaitonde's user avatar
7 votes

Gaussian elimination is just Gram-Schmidt with a change to the inner product symbol?

I'm not sure how well this will answer the question "why does this happen?" But hopefully will provide more geometric/abstract views of this. It seems to me that the Gram–Schmidt and ...
Callum's user avatar
  • 877
6 votes
Accepted

How can one construct a sparse null space basis using recursive LU decomposition?

On the LUQ decomposition The algorithm implemented in luq (see reference given below) computes bases for the left/right null spaces of a sparse matrix $A$. ...
Nawaf Bou-Rabee's user avatar
6 votes
Accepted

Matrix equation with Hadamard product and its own inverse involved

Removing all unnecessary parameters, we come to the equation $\Omega^{-1}=2 W\odot \Omega + B$ where $B$ is positive definite. We need to find a solution in the cone $M_+$ of positive definite ...
fedja's user avatar
  • 59.5k
6 votes
Accepted

When are two binary matrices simultaneously equivalent to their transpose?

Clearly, a necessary condition is that for every word $w$ in two letters, one has $${\rm Tr}\,w(A^t,B^t)={\rm Tr}\,w(A,B).$$ Equivalently, $${\rm Tr}\,\hat w(A,B)={\rm Tr}\,w(A,B),$$ where $\hat w$ is ...
Denis Serre's user avatar
  • 51.5k
6 votes
Accepted

Spectrum of operator involving ladder operators

Q: Does anybody know how to numerically overcome this pseudospectral effect? The key idea is "normal ordering". Rewrite the problem in such a way that annihilation operators $a$ appear to ...
Carlo Beenakker's user avatar
5 votes

Behaviour of eigenspaces of adjacency matrices after a single change to the graph

What I'm about to say applies to the eigenvalues (at least). Here's what comes to my mind - it sprung from memory of some results of Batson, Spielman and Srivastava, mostly the paper "Twice Ramanujan ...
amakelov's user avatar
  • 987
5 votes

What is the time complexity of truncated SVD?

According to the man page of svds, provided by MATLAB, svds is currently based on "Augmented Lanczos Bidiagonalization Algorithm" when it comes to the top-$k$ SVD computation of a large-...
fitfall's user avatar
  • 51
5 votes

Is this inequality involving the Frobenius norm right?

As stated$^*$ this problem has nothing to do with the Frobenius norm. The map $T: A \mapsto AG$ is a linear transformation from a finite-dimensional vector space, so for any norms we have a constant $...
Noam D. Elkies's user avatar
5 votes
Accepted

In a large sparse matrix, how many eigenvalues/eigenvectors are “spurious”?

Antisymmetric matrices are normal, hence they can be diagonalized with an orthogonal matrix. So $\|A\|_F^2=\sum |\lambda_i|^2$. If you keep only the $k$ largest eigenvalues (ordered in modulus: $|\...
Federico Poloni's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible