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
29 votes
2 answers
1k views

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

I noticed at some point that if you take the Gram-Schmidt algorithm for taking the QR decomposition of a matrix, and you change the meaning of the inner product symbol $\langle \mathbf u, \mathbf v \...
wlad's user avatar
  • 4,823
21 votes
3 answers
48k views

What is the time complexity of truncated SVD?

Full SVD, on an $m \times n$ matrix $A$, [U,S,V] = svd(A), would cost $O(m^2n + mn^2 + n^3)$ time. But what is the time complexity if we only need the $k$ largest ...
user40484's user avatar
  • 327
20 votes
2 answers
17k views

Complexity of linear solvers vs matrix inversion

Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given ...
Alm's user avatar
  • 1,159
17 votes
4 answers
6k views

Why is fast matrix multiplication impractical?

I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication. I read some content saying fast matrix multiplications are impractical because of large ...
Jiawei Ren'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
9 answers
9k views

Exponential of large matrices

I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse. Does anyone have a ...
Xodarap's user avatar
  • 151
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
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
14 votes
3 answers
14k views

Interesting relationships between Cholesky decomposition and diagonalization

Let $\Sigma$ be a hermitian positive definite matrix and $L$ be its Cholesky decomposition so that $LL^\ast=\Sigma$. Furthermore, let's diagonalize $\Sigma$ as $\Sigma = P\Lambda P^\ast$. $\Lambda$ is ...
Arthur B's user avatar
  • 1,882
13 votes
0 answers
566 views

What are the difficulties in proving almost-everywhere stability of Gaussian elimination?

It is well known that Gaussian elimination without pivoting is numerically unstable, and in practice Gaussian elimination is done with row pivoting (partial pivoting). A theorem of Wilkinson states ...
Christopher A. Wong's user avatar
12 votes
2 answers
8k views

What is the time complexity of the matrix exponential?

While trying to compute the Matrix Exponential of an $n \times n$ array I decided to take advantage of a Python function called scipy.linalg.expm(). According to ...
FaCoffee's user avatar
  • 241
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
810 views

Determinant and eigenvalues of a specific matrix

This came up in a conversation with an engineer friend of mine. Let $c>0$ be a constant. Let $A_{ij}$ be an $n$ by $n$ matrix with entries $$ A_{ij} = e^{-c(i-j)^2}. $$ Is there a name for this ...
Lev Borisov's user avatar
  • 5,166
11 votes
1 answer
867 views

Decide if a matrix is transposable

A matrix $M$ is called transposable if it can be transformed into its transpose $M^t$ via row and column permutations. Is there an efficient a way/algorithm to decide if a given matrix is ...
Stefan Blausberg's user avatar
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
11 votes
3 answers
8k views

Eigenvectors of a symmetric positive definite Toeplitz matrix

I wish to efficiently compute the eigenvectors of an n x n symmetric positive definite Toeplitz matrix K. A full eigendecomposition would be even better. Although I assumed this would be a well ...
Sodalite's user avatar
  • 111
11 votes
1 answer
584 views

Solving $AXB + X\odot C = D$

I need to solve the following equation for $X$ with $d$-by-$d$ matrices $A,B,C,D$ and Hadamard product $\odot$ $$AXB + X\odot C = D$$ Vectorizing all terms gives a solution with $O(d^6)$ complexity, ...
Yaroslav Bulatov's user avatar
11 votes
2 answers
947 views

Existence of sparse LU decomposition of sparse matrix

Let $A$ be a sparse matrix over some field. I would like to know about the existence of LU decompositions so that $L,U$ are both sparse. More precisely, let $A$ be an $N$-by-$N$ matrix. Suppose each ...
Matt Hastings's user avatar
11 votes
0 answers
719 views

Fast computation of matrix product $AXA^T$ with fixed $A$?

Suppose we have two $n$-by-$n$ matrices $X$ and $A$, where $A$ is known and $X$ may change in different invocations, and we want to compute $AXA^T$. Is there an algorithm that beats the naive one of ...
hao chen's user avatar
11 votes
1 answer
2k views

Quantifying the failure of the Cholesky factorization test for indefinite matrices

The Cholesky factorization is the classic test to check if a matrix is positive definite. In infinite precision it is also an exact test: A matrix has a Cholesky factorization iff it is positive ...
alext87's user avatar
  • 3,167
9 votes
2 answers
1k views

polynomials with minimal $L_\infty$ norm on multiple disjoint intervals

It is well-known that Chebyshev polynomials are the polynomials of minimal $L_\infty$ norm on [-1,1] with leading coefficient 1. But what if you want the minimal $L_\infty$ polynomial on two disjoint ...
Paul's user avatar
  • 223
9 votes
1 answer
436 views

$M = AA^t$ where $A$ has unit norm columns

Let $M \in \mathbb{R}^{k\times k}$ positive definite with $\operatorname{tr} M = m$, where $m$ is an integer such that $m \geq k$. I have found a way (using this answer) to decompose $M = AA^t$ with $...
Yair Daon's user avatar
  • 185
9 votes
1 answer
524 views

What is the Lipschitz constant of the differential of the matrix exponential $\mathfrak{so}(3)\to \mathrm{SO}(3)$

I'm interested in numerical methods on $\mathrm{SO}(3)$ manifold, and working on a particular problem using the exponential coordinates: $$ R(u) := \exp(u_\times) $$ with $u\in \mathbb{R}^3$ and where ...
Maciej's user avatar
  • 111
8 votes
2 answers
368 views

How to obtain the rational solution of a linear system efficiently?

Suppose that I have a linear system $AX=b$ with $A\in\mathbb{Z}^{n\times m}$ and $b\in\mathbb{Z}^{n}$. Assume that $AX=b$ has exactly one rational solution. Then how can I obtain this solution ...
Jie Wang's user avatar
  • 133
8 votes
1 answer
1k views

Finding Toeplitz matrix nearest to a given matrix

For an arbitrary $N\times N$ Hermitian matrix $A$, I want to derive a Toeplitz matrix from $A$ such that the eigenvectors of both matrices have minimal change. Specifically I want find the Toeplitz ...
Creator's user avatar
  • 435
8 votes
2 answers
4k views

Finding the smallest eigenvalues of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $M$. $M$ is a Laplacian matrix, and it has the following structure: $...
Jeff's user avatar
  • 500
8 votes
1 answer
462 views

When are two binary matrices simultaneously equivalent to their transpose?

For any real square matrix $A$ there is an invertible matrix $P$ such that $A^t = P^{-1}AP$. I have two binary ($0,1$) matrices $A$ and $B$. When does there exist a $P$ such that $A^t = P^{-1}AP$ and $...
Supriyo's user avatar
  • 343
8 votes
1 answer
1k views

Computation time of Smith normal form in Maple

I am using Maple to compute the Smith normal form (SNF) of a $120 \times 120$ matrix and it seems that I will never get an answer back. I have checked my code for small cases and I believe that it is ...
Yibo Gao's user avatar
  • 346
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
8 votes
0 answers
450 views

Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method. In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...
arbitUser1401's user avatar
7 votes
3 answers
1k views

Checking positive semi-definiteness of integer matrix

Key Problem : Is there any theorem about eigenvalues or positive semi-definiteness of small size matrices with small integer elements? I have to check positive semi-definiteness of many symmetric ...
SIM2's user avatar
  • 73
7 votes
2 answers
516 views

Linear equations with absolute values

Assume we have a set of equations in $x \in \mathbb{R}^n$ $$|a_i\cdot x|=b_i$$ where $a_i \in \mathbb{R}^n$ and $b_i>0$ are given. Could such a system be solved efficiently? In a theoretical ...
Doron Shafrir's user avatar
7 votes
1 answer
389 views

Minimize spectral radius with orthogonal matrix

Let $A$ be a real square and invertible matrix. I would like to find $$ s(A) = \min_U \rho(U A), $$ Where $U$ is orthogoal, i.e. $U U^T = I$ and $\rho(A)$ is the spectral radius, i.e. the largest ...
Jiro's user avatar
  • 909
7 votes
2 answers
304 views

A system of non-linear equations that is decomposable as a product -- uniqueness of solution?

I have a system of non-linear equations $ a_1=f_0 g_1$ $a_2=f_1 g_1 + f_0 g_2$ $a_3=f_2 g_1 + f_6 g_2 + f_0 g_3 $ $a_4=f_3 g_1 + f_7 g_2 + f_6 g_3 + f_0 g_4 $ $a_5=f_4 g_1 + f_8 g_2 + f_7 g_3 + ...
Kass's user avatar
  • 243
7 votes
2 answers
8k views

Conditions for convergence of Euler's method

It is known that a sufficient and necessary condition for $$\dot y(t) = f(y(t), t), \quad t > 0, \quad y(0) = y_0$$ to have a unique solution is $f$ Lipschitz in $y$ and continuous in $t$. However, ...
John Wong's user avatar
  • 753
7 votes
1 answer
228 views

Numerical method for simultaneous computation of eigenvalues of a family of commuting matrices

I have a problem where I have $n$ commuting matrices $M_1,\dots,M_n$. It is a well-known fact that commuting matrices are simultaneously diagonalizable/triangularizable. I need to find the eigenvalues ...
Hayden Ringer'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
7 votes
1 answer
196 views

Compute only selected components of an eigenvector

I am wondering whether it is possible to compute portions of the eigenvectors of a given (possibly very big) matrix. More formally, consider the eigenvalue problem $\mathbf{Ax} = \lambda \mathbf{x}$, ...
gboukensha's user avatar
7 votes
1 answer
307 views

Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?

Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...
Kirk S.'s user avatar
  • 325
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
2 answers
231 views

Finding $\theta$ such that at least one eigenvalue of $A(\theta)$ is real

Is there a known method to find a set of $\theta$ such that at least one eigenvalue of $A(\theta)$ is purely real? Assume $A(\theta)$ is a real square matrix whose elements are linear functions of a ...
CWC's user avatar
  • 359
7 votes
1 answer
330 views

Is there any sort of higher-order SVD (quadratic and above) for dimensionality reduction?

(Posted this on math.stackexchange and cross.correlated over more than a week ago, but didn't get an answer, and this is a question in my research so this seems like it might have been the better ...
user650261's user avatar
7 votes
1 answer
989 views

Norm of inverse confluent Vandermonde matrix

Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as $$V= \begin{bmatrix} v_{1,0}&v_{2,0}&\dots&...
dima's user avatar
  • 949
7 votes
0 answers
114 views

Are there attempts to numerically finding algebraic structures over finite-dimensional vector spaces?

By "algebraic structure" I mean a finite set of linear operators between tensor products of copies of one (or more) finite-dimensional (complex or real) vector spaces, fulfilling a set of ...
Andi Bauer's user avatar
  • 2,901
7 votes
0 answers
188 views

A special eigenvalue problem

For my research I need to solve a generalised eigenvalue problem $Ax=\lambda B x$, where $A$, $B$ are general matrices, and selectively find only eigen-pairs $\lambda, x$ such that $\lambda\in \mathbb{...
yarchik's user avatar
  • 482

1
2 3 4 5 6