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_{\...

40
votes

### How fast can we *really* multiply matrices?

Recently there is a PhD thesis, Practical fast matrix multiplication algorithms, about the practical fast matrix multiplication algorithms like Strassen:
Matrix multiplication is a core building ...

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.)
...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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}(...

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 ...

9
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 ...

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 ...

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, ...

8
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 ...

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 ...

7
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 ...

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 ...

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 ...

7
votes

Accepted

### rank of an integer valued matrix

Note that if you take a prime $p$ and treat the matrix $A$ as a matrix $A'$ over $\mathbb{Z} / p \mathbb{Z}$, then from the property of $\operatorname{rank}(A)$ being the largest order of a non-zero ...

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 ...

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$. ...

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 ...

6
votes

Accepted

### Usage and origin of the terms dictionary and atom in compressed sensing

The terms "dictionary" and "atoms" predate compressed sensing, they are more generally used in signal processing. An example is the Gabor atom for wavelets. For an early use of &...

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 $...

5
votes

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

Not the same algorithm, but here is an alternative that I have used in a recent paper; you can put it together quickly with standard Matlab functions if $A$ is a $m\times n$ matrix with $m\ll n$ (like ...

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

#### Related Tags

numerical-linear-algebra × 296linear-algebra × 193

matrices × 99

na.numerical-analysis × 99

eigenvalues × 33

matrix-analysis × 22

algorithms × 17

eigenvector × 16

oc.optimization-and-control × 13

matrix-theory × 13

sparse-matrices × 13

reference-request × 12

matrix-equations × 11

nonlinear-optimization × 10

fa.functional-analysis × 9

computational-complexity × 9

convex-optimization × 8

linear-programming × 8

matrix-inverse × 8

factorization × 7

tensor × 6

perturbation-theory × 6

block-matrices × 6

multilinear-algebra × 5

numerical-analysis-of-pde × 5