All Questions
Tagged with linear-algebra na.numerical-analysis
12 questions
21
votes
9
answers
19k
views
What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix?
see title.
An algorithm is 'good' if it is able to distinguish between zero Eigenvalues and nonzero Eigenvalues.
- 979
13
votes
2
answers
946
views
Computing a large permanent
Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix?
I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...
- 6,962
12
votes
2
answers
5k
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 ...
- 253
11
votes
1
answer
3k
views
Best way to find a closest vector in a lattice
Let $v_1,\dotsc,v_n$ be linearly independent vectors in $\mathbb{R}^n$, and let $\Lambda=\bigoplus_{i=1}^n \mathbb{Z}v_i$. The question is, given a vector $w$ in $\mathbb R^n$, find the element $v$ ...
- 351
10
votes
1
answer
449
views
How to compute $\sum_{x \in \mathbb{Z}^n} e^{-x^TMx}$ efficiently
Let $M$ be a real symmetric integer valued positive definite matrix with $\det(M) \geq 1$. I would like write code to compute
$$S_M= \sum_{x \in \mathbb{Z}^n} e^{-x^TMx}.$$
One option is to simply ...
- 3,377
8
votes
5
answers
15k
views
Eigenvalues of A+B where A is symmetric positive definite and B is diagonal
If I have a symmetric positive definite matrix A and a diagonal matrix B, and I know the eigenvalues of both A and B (by iterative numerical computation in A's case and trivially for B), is there any ...
- 135
7
votes
4
answers
2k
views
Is there a name for the matrix equation A X B + B X A + C X C = D?
I happen to be working on a problem that reduces to solving the following equation:
$$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$
where A through D are known matrices ( A, B, D ...
- 1,890
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
1
answer
505
views
Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently
What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$?
Do we have to calculate $A^{-1}b$, or is this not necessary?
edit: I forgot to mention that A is symmetric and ...
- 493
6
votes
1
answer
737
views
Rank of the absolute-value matrix $|M|$ vs. rank of $M$
Let $M$ be a real matrix of rank $r$ (and let us set $M=UV^T$, with $U,V^T\in\mathbb{R}^{n\times r}$, to fix the notation).
Let $|M|$ be the matrix obtained by taking the absolute value of each entry ...
- 20.2k
4
votes
1
answer
721
views
Singular value decomposition of truncated discrete Fourier transform matrix
Let $\mathbf{F}$ be a discrete Fourier transform (DFT) matrix such that
\begin{align}
F_{m,n}=e^{-j2\pi(m-1)(n-1)/N},\quad m,n=1,\ldots,N.
\end{align}
What we can say about the singular value ...
- 287
3
votes
0
answers
2k
views
Eigenvalue Problems with Linear Constraints
The motivation for this problem comes from trying to develop a simple way to decompose domains into non-overlapping subdomains to solve for the eigenvalues of some differential operator. The idea is ...
- 543