All Questions
Tagged with numerical-linear-algebra matrices
100 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
21
votes
3
answers
51k
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 ...
- 327
21
votes
2
answers
18k
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 ...
- 1,207
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 ...
- 279
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
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 ...
- 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 ...
- 947
12
votes
2
answers
9k
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 ...
- 241
11
votes
2
answers
821
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 ...
- 5,186
11
votes
1
answer
896
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
...
- 111
11
votes
3
answers
9k
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 ...
- 111
11
votes
0
answers
764
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 ...
- 75
9
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 ...
- 356
9
votes
1
answer
472
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 $...
- 185
8
votes
1
answer
2k
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 ...
- 495
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
8
votes
1
answer
1k
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&...
- 959
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 ...
- 73
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
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
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
2
answers
244
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 ...
- 433
7
votes
0
answers
197
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{...
- 492
6
votes
2
answers
2k
views
Complexity of rectangular matrix multiplication
I am interested in the complexity of multiplying two matrices $A$ and $B$, i.e. to compute $AB$.
From [Le Gall and Urrotia], I know that:
if $A$ and $B$ are square-matrices of size $n$, then this can ...
- 562
6
votes
1
answer
830
views
Dominant eigenvector of a real symmetric tridiagonal matrix
What is the most efficient way to calculate the dominant eigenvector of a real symmetric tridiagonal matrix? What's the corresponding time complexity bound?
Could someone give me a reference for ...
- 61
6
votes
1
answer
305
views
For a set of matrices $S$, find $X$ such that the elements of $SX$ commute
Let $S := \{A_0, A_1, \dots, A_d\}$, where $A_k \in \mathbb{C}^{n \times n}$, be a set of (generally noncommuting) matrices. I am interested in finding a nonsingular $X \in \mathbb{C}^{n \times n}$ ...
- 300
6
votes
1
answer
621
views
Tensor matricizations and their decompositions
Suppose we have a 4-index tensor $t_{ijkl}$ (all 4 dimensions are equal size). We can make a matrix out of it by taking first and last two indexes as new indexes: $t_{ijkl} \rightarrow M_{ij, kl}$. ...
- 71
6
votes
0
answers
141
views
Algorithm to check a conjectural value for the rank of a large matrix
Feel free to suggest a different title, I'm not sure how to phrase this. I'm in the following somewhat specific situation:
I'm checking a conjecture which at the end of the day boils down to the ...
- 8,524
5
votes
2
answers
4k
views
Are there any algorithms for solving nonlinear matrix equations over $\mathbb{C}$?
Are there any algorithms for solving nonlinear matrix equations over $\mathbb{C}$?
I am especially interested in solving polynomial nonlinear matrix equations.
For instance, let $X$ be some matrix ...
- 1,503
5
votes
2
answers
6k
views
Computing the largest eigenvalue of a very large sparse matrix
I am trying to compute the asymptotic growth-rate in a specific combinatorial problem depending on a parameter $w$, using the Transfer-Matrix method. This amounts to computing the largest eigenvalue ...
- 233
5
votes
1
answer
403
views
Best orthogonal approximation of rank 1 matrix
Let $X=\lambda_0u_0v_0^T\in\mathbb{R}^{n\times n}$ be a rank 1 matrix where $\lambda_0\in\mathbb{R}$, $u_0,v_0$ are of unit Euclidean norm. What is the solution of the following problem?
$$\hat{X}=\...
- 1,495
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
5
votes
1
answer
251
views
Smooth, non-analytic functions of non-normal matrices
My apologies if this isn't a well-enough-posed question, I think I'm partly unsure of what exact question to even ask.
There are many different ways in which we can take a function of a matrix.
We ...
- 854
5
votes
0
answers
392
views
Preconditioner for finding the smallest eigenpairs 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 $L$. $L$ is a graph Laplacian, with the following structure: $L = D -...
- 500
5
votes
0
answers
112
views
Inverses of the sums of all possible subsets of a set of symmetric and positive definite matrices
I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e.
$(A_1+A_2)^{-1},(A_1+A_3)^{-1},(A_2+A_3)...
- 71
4
votes
3
answers
3k
views
Is this inequality involving the Frobenius norm right?
Let $A$ be a generic (or varying) square, real $ n \times n$ matrix. Let $G$ be a fixed $n \times k$ matrix, $k < n.$ Denote by $||.||_F$ the Frobenius norm.
Is it true that $||AG||_F \geq c(G) ||...
- 1,465
4
votes
2
answers
948
views
Numerically solving for pseudo inverse of non-squared Vandermonde matrix
I have a linear system to solve, set up as:
$\bf{Ax}=\bf{b}$
with a non-squared matrix A,
$
\bf{A}=
\begin{bmatrix}
1 & A_{1} & A_{1}^2 & \cdots & A_{1}^n \\
1 & A_{2} & A_{...
- 41
4
votes
1
answer
4k
views
Numerical trace of inverse matrix from Cholesky
This question was somewhat answered here: Fast trace of inverse of a square matrix. However, I feel like there was no complete answer wrt the Cholesky case.
I have the matrix $\Sigma=LL^T$. Is there ...
- 171
4
votes
1
answer
295
views
Is there a fast algorithm to test positivity of all principal minors of non-symmetric matrix?
I have a matrix $A \in \mathbb{R}^{n \times n}$ with positive eigenvalues. In the symmetric case, Sylvester's criterion implies that all the principal minors are positive. In the non-symmetric case, ...
- 188
4
votes
1
answer
750
views
submatrix of a given size with maximum frobenius norm
Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
- 859
4
votes
0
answers
149
views
Zero diagonal nonsymmetric block checkerboard matrix: orbits and numerical ranges
Let $A \in \mathbb{R}^{m \times m}$ be a nonsymmetric zero diagonal matrix with a zero/non-zero pattern which is symmetric and persymmetric (i.e. symmetric in the northeast-to-southwest diagonal).
If ...
- 323
4
votes
0
answers
2k
views
What is the time complexity of the largest singular value and its vectors?
Full zero-error SVD on an $m \times n$ matrix $A$ would cost $O(\min(m^2n,mn^2))$. What is the time complexity if we need only the largest singular value and its corresponding vectors? I think it is $...
- 123
4
votes
0
answers
578
views
Determining whether a Schur complement is invertible
Consider the symmetric matrix
$$M = \begin{bmatrix}
A & B \\
B^T & -C
\end{bmatrix}$$
where $A \in \cal{R}^{n \times n}$ and $C \in \cal{R}^{m\times m}$ are symmetric, ...
- 41
3
votes
2
answers
3k
views
Sparse approximation of the inverse of a sparse matrix
Is it possible to approximate an inverse of a sparse matrix with a sparse matrix?
The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...
- 2,205
3
votes
2
answers
2k
views
Matrix equation with Hadamard product and its own inverse involved
I know there is an almost exactly same question here but I have further specifications. So my problem is as follows:
$$
\Omega^{-1}=\dfrac{1}{n}\left(\Omega\odot \mathbf{W}+\mathbf{X}'\mathbf{X}+\...
- 133
3
votes
2
answers
216
views
What are interesting heuristics of determining how far given matrix is from a singular one?
The condition number and volume of matrix (defined as absolute value of its determinant) are things which come to mind. Is there more?
I think that over the years numerical folks (who are faced with ...
- 355