Questions tagged [numerical-linear-algebra]
{numerical-linear-algebra} questions involving algorithms for linear algebra computations.
305 questions
1
vote
1
answer
61
views
Efficient construction of an orthogonal matrix with prescribed diagonal quadratic forms
Let $\boldsymbol{\lambda}=(\lambda_1,\dots,\lambda_n)$ and $\mathbf{d}=(d_1,\dots,d_n)$ be two vectors of real numbers sorted in non‑increasing order, satisfying the majorization conditions
$$
\sum_{i=...
- 4,190
0
votes
0
answers
24
views
Simple GMRES and standard GMRES coefficient matrices
I am studying Homer F. Walker and Lu Zhou's "A simpler GMRES", Numer. Linear Algebra Appl. 1, No. 6, 571-581 (1994), MR1310986, Zbl 0838.65030, and if I understand this correctly, what one ...
- 101
19
votes
6
answers
1k
views
Fast matrix-vector multiplication for a fixed 0-1 matrix
I have a fixed $n \times n$ matrix $M$ whose entries are all either $0$ or $1$. I want to compute the product $Mv$ for various vectors $v \in \mathbb{R}^n$ (or over other fields/rings and abstract ...
- 390
0
votes
0
answers
214
views
Practical partial fraction decomposition
I have tried to implement Ramanujan's algorithm for Solvability of a system of polynomial equations but got stuck in the final step of calculating the partial fraction decomposition from which the ...
- 14.3k
1
vote
0
answers
73
views
Handling defective eigenvalues in shifted block Lanczos algorithm
I’m implementing a shifted version of the block Lanczos algorithm, following the approach described in the paper by Lewis, Simon, and Grimes , to solve generalized eigenvalue problems. My ...
- 11
6
votes
1
answer
245
views
Bounds on the largest singular value computable in $O(n^2)$
Consider an $n \times n$ matrix $A$. I'm interested in algorithms that can verify whether the largest singular value of $A$, i.e., its spectral norm $\| A \|_2$, is less than or equal to $1$ or not. ...
- 279
0
votes
0
answers
97
views
Convergence rate of Hermitian QR iteration
Suppose $A$ is an $n \times n$ dimensional Hermitian matrix with $\|A\| \le 1$. I now consider the QR algorithm. I set $A_0 = A$ and at the $k$th step compute the QR decomposition $A_k = Q_k R_k$ and ...
- 81
0
votes
1
answer
143
views
Eigenvectors for specific eigenvalues
When reading the following paper:
Ed S. Coakley, Vladimir Rokhlin, A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices, Applied and Computational ...
1
vote
1
answer
205
views
Condition number of preconditioned positive definite matrix
Can we find a symmetric positive definite matrices sequence $\{A\}$ with fixed dimension, such that
$$ \frac{\kappa \left( D^{-1} A \right)}{\kappa(A)} > 1,$$
where $\kappa(M):=\frac{\lambda_{\max}(...
- 57
5
votes
0
answers
428
views
On computing the condition number of SPD matrices via convex optimization
Suppose that we have an $n \times n$ symmetric positive definite (SPD) matrix $\bf Q$ and that we would like to compute its condition number via convex optimization. In section 3.2 of Boyd et al.$^\...
- 2,578
0
votes
2
answers
225
views
Optimization algorithms for Kronecker approximation of high-dimensional covariance matrices
I'm working with a high-dimensional covariance matrix and exploring Kronecker product approximations to make it computationally manageable.
Here's the setup:
I have a graph $G$ represented by a $D\...
- 1
3
votes
1
answer
445
views
A problem about matrix inverse and regularization methods
I'm researching the problem of solving the equation $A\mathbf{x}=\mathbf{b}$ with ill-conditioned matrices. We know that if we solve it directly, like $\mathbf{x}=\mathrm{inv}(A)\ast\mathbf{b}$, then ...
- 33
2
votes
1
answer
178
views
Is it possible to solve this kind of quadratic simultaneous equations?
$$\mathbf{x} = (x_1, x_2, ..., x_N)^T \in \mathbb{R}^{N} \\
\mathbf{A}_i \in \mathbb{R}^{N \times N},
\mathbf{b}_i \in \mathbb{R}^N ,
\mathbf{c}_i \in \mathbb{R}\\
\mathbf{x}^T\mathbf{A}_i\mathbf{x}...
- 23
2
votes
1
answer
332
views
Usage and origin of the terms dictionary and atom in compressed sensing
In compressed sensing two terms or perhaps fancy word are frequently encountered. One is the dictionary and the other is atom. The dictionary is the matrix and its columns are called "atoms" ...
- 943
23
votes
0
answers
647
views
Why does the random shift in the QR eigenvalue algorithm work in the non-symmetric case over the complex field
I tried to implement the QR algorithm for non-symmetric matrices with complex entries to show to my students. The main part of the implementation was standard: the Householder reduction to the ...
- 64.4k