All Questions
Tagged with numerical-linear-algebra matrices
100 questions
3
votes
1
answer
143
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
1
vote
1
answer
293
views
Nearest Kronecker product to sum of Kronecker products
I am interested in efficiently finding the closest Kronecker decomposition to the sum of $k$ Kronecker products:
$$\min_{A,B} || A \otimes B - \sum_{i=1}^k A_i \otimes B_i ||_F$$
where $A,A_i$ are $p \...
- 111
1
vote
0
answers
95
views
Vandermonde-type factorization of moment matrix?
Consider $n,d \in \mathbb{N}_{>0}$, there are many functions $y:\mathbb{N}^{n} \to \mathbb{R}$. Now for simplicity, we denote $y(\alpha)$ to be $y_{\alpha}$. Let $|\alpha| = \sum_{i=1}^{n}\alpha_{i}...
- 275
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
1
vote
0
answers
179
views
QR algorithm for eigenvalues and eigenvectors of large symmetric matrices
I am trying to write a QR algorithm in Python for eigenvectors and eigenvalues finding for large symmetric matrices,
My initial thought was to use Householder transformation with a Wilkinson shift ...
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
3
votes
1
answer
332
views
Complexity of inverting and multiplying against a symmetric Toeplitz matrix with two repeated entries
I know that the computational complexity of inverting a general $n \times n$ matrix $A$ is $O(n^{2.373})$ and multiplying it against an $n \times m$ matrix is $O(n^2m)$. Moreover, I've seen that ...
- 91
1
vote
1
answer
331
views
Eigenvalues of a circulant: DFT or Inverse DFT Convention?
Currently, most engineering texts (and webpages including Wikipedia) define forward discrete Fourier transform with a negative sign on the exponential. This is a convention and the inverse discrete ...
- 879
0
votes
0
answers
232
views
How to analyse the range of eigenvalues of a symmetric and indefinite matrix?
Let $G$ be a symmetric and indefinite matrix defined as follows
$$ G := S - \begin{pmatrix} I_n & I_n \\ I_n & I_n \end{pmatrix},$$
where $S$ is a symmetric positive definite matrix of size $...
- 1
1
vote
0
answers
111
views
Solving a block tridiagonal system with diagonal perturbations
Say we have a block tridiagonal matrix, $T \in \mathbb{R}^{NL \times NL}$, with constant off diagonals, $\mathbf{B} \in \mathbb{R}^{L\times L}$, given by
$$
T = \begin{bmatrix} \mathbf{A}_1 & \...
- 11
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
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
3
votes
2
answers
2k
views
Iterative methods for linear system with non-diagonally dominant matrix
I have a linear system
\begin{align*}
\left[\begin{array}{cccc}
1 & 2 & 1 & -1 \\
3 & 2 & 4 & 4 \\
4 & 4 & 3 & 4 \\
2 & 0 &...
- 65
0
votes
1
answer
319
views
Correct way to conduct equilibrium scaling of linear/integer/MIP program
I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...
- 21
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
2
votes
1
answer
421
views
Is it possible to obtain orthogonal (but not normalized) vectors after QR factorization?
After QR decomposition of a matrix, $M$, the columns of Q are orthonormal. Is it possible after obtaining Q, we recover unnormalized column vectors from $Q$? For example, the matrix M has the ...
- 879
3
votes
0
answers
147
views
Convolution integral and its matrix representation
My background is chemistry and I was exploring some one dimensional deconvolution problems i.e., resolution of two or more overlapping peaks. A lot of excellent work was done in the 1970-80s. However, ...
- 879
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
0
votes
0
answers
226
views
Decomposition of symmetric block matrix
I came across this question and got really interested about it. There, the OP asks whether is possible to decompose a $2n \times 2n$ block matrix:
$$ \begin{pmatrix}
X & I \\
I & Y
\end{...
0
votes
1
answer
266
views
Using QR or SVD to sum up finite number of matrices
Problem
I was wondering if there are any theoretical results that tackle the following problem:
Construct the following matrices $\mathbf{\mathcal{S}_{1}},\mathbf{\mathcal{S}_{2}},\ldots,\mathbf{\...
2
votes
1
answer
164
views
The "best way" to order unknowns in linear systems
Start with a linear system of the form
\begin{equation*}
Ax + Bt + C = 0,
\end{equation*}
where $x = (x_1, \dots, x_n) \in \mathbb R^n$ is the vector of unknowns, $t \in \mathbb R^m$ is a vector of ...
- 41
1
vote
0
answers
78
views
Is there an efficient way to do semidefinite programming with a Lyapunov equation constraint?
I am trying to numerically solve semidefinite programs of the form
$$\begin{array}{ll} \underset{X,Y}{\text{minimize}} & \operatorname{tr}(AX)\\ \text{subject to} & BY + YB = X\\ & X, Y \...
- 31
1
vote
0
answers
191
views
What is the solution of the matrix equation $A X + X A' + B X B' + C = 0$ for $X$?
I know that the matrix equation $A X + X A' + C = 0$ is in the form of the time-continuous Lyapunov equation, so solving for $X$ is pretty trivial since the solution already and numeric solvers ...
- 11
3
votes
2
answers
244
views
A problem about determinant and matrix
Suppose $a_{0},a_{1},a_{2}\in\mathbb{Q}$, such that the following determinant is zero, i.e.
$
\left |\begin{array}{cccc}\\
a_{0} &a_{1} & a_{2} \\
\\
a_{2} &a_{0}+a_{1} & a_{1}+a_{...
0
votes
1
answer
535
views
Conditions to solve linear system with matrix blocks
How to verify if a linear system of symmetrical matrix blocks has solution?
I have the matrix:
$\left[M\right]_{p \times p}$, symmetrical
$\left[G\right]_{p \times q}$
and then, I would like to ...
- 253
0
votes
1
answer
230
views
Solution of complex linear system
In Brubeck, Nakatsukasa, and Trefethen - Vandermonde with Arnoldi (example 3) they solve the following linear system:
$$\operatorname{Re}\left(\begin{array}{ccc}1 & \cdots & z_{1}^{n} \\ 1 &...
- 45
1
vote
1
answer
146
views
Norm of a matrix with clustered eigenvalues
On page 271 of Trefethen and Bau's Numerical Linear Algebra, it is constructed a matrix
$$A=2I_{m\times m}+0.5\cdot\frac{\text{rand}(m)}{\sqrt{m}}$$
for $m=200$, where rand(m) is an array with $m\...
- 13
1
vote
1
answer
326
views
For the purposes of solving linear equations, is there a fast decomposition that works for all Hermitian matrices?
Let $A$ be an arbitrary Hermitian matrix. Is there a way of efficiently factorizing $A$ for the purposes of solving $Ax = b$ for arbitrary $b$?
There are two decompositions I'm aware of that nearly ...
- 4,943
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
1
vote
0
answers
121
views
Algorithm for the nilpotence of matrix polynomials
Let $P$ be a multivariate polynomial of real-valued $N \times N$ matrices. Given $X_1, X_2, ..., X_M \in \mathcal{M}_N\{\mathbb{R}\}$, is there any optimal algorithm to determine whether the result of ...
- 19
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
1
vote
1
answer
321
views
Solve linear system with bordered positive definite matrix
I want to solve the usual $A x = b$ system. In block form:
$$ \begin{bmatrix} B & c \\ c^{T} & 0 \end{bmatrix} \begin{bmatrix} x' \\ x_{n+1} \end{bmatrix} = \begin{bmatrix} b' \\ b_{n+1} \end{...
- 139
3
votes
2
answers
505
views
Updating the null space of a matrix
I am facing a problem where I have to find any (nontrivial) vector x such that Ax=0, where A is a rectangular nxm matrix with m>n, so the problem is underdetermined. I must find this x for A, but ...
- 33
0
votes
0
answers
41
views
Orthogonality condition of symmetric matrix pencil
Let $P(\lambda)=\lambda M−L\in \mathbb{R}^{n \times n}$ be a matrix pencil with symmetric nonsingular matrix $M$ and $L$ is a weighted Laplacian matrix of a connected graph. Clearly $(0,1_n)$ is an ...
- 21
1
vote
1
answer
275
views
Action of square root of tridiagonal matrix product on vector
Assume nonsymmetric, tridiagonal matrices $A, B \in \mathbb{R}^{n\times n}$ (where $n$ is in the order of 1000) and $A, B, AB$ are diagonalizable and have positive eigenvalues.
How do you efficiently ...
- 213
2
votes
1
answer
556
views
How to solve a quadratic matrix equation with positive semidefinite constraint?
I have the following quadratic matrix equation:
$$ XAX+X = B $$
where both $A$ and $B$ are given positive definite matrices, and $X$ is a covariance matrix and, hence, positive definite.
When there is ...
- 101
2
votes
0
answers
52
views
Large-scale projected minimum-eigenvalue computations
I am interested in efficient numerical procedures for solving large-scale instances of the following projected minimum-eigenvalue problem:
$$\mu := \min_{v \in \mbox{ker}(A)} \frac{v^T H v}{\lVert v \...
- 35
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
2
votes
1
answer
1k
views
Is it faster to compute eigenvalues or coefficients of characteristic polynomials?
Given $A \in \mathsf{M}_n(\mathbb{C})$ (no special structure) is it (generally) faster to compute its eigenvalues or the coefficients of its characteristic polynomial?
References/insights would be ...
- 1,719
5
votes
1
answer
401
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
3
votes
2
answers
674
views
Parametrising a sparse orthogonal matrix
I need to find a way to parametrise a matrix that is both sparse (to some degree) and orthogonal, i.e., I am looking for a parametrisation that describes $A \in \mathbb{R}^{n\times m}$ such that $AA^𝑇...
- 123
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
0
votes
1
answer
116
views
Matrix equation of the form $C A C^\intercal = D$
Consider the following square matrix
\begin{align}
A = \left(\matrix{d & 0 & -\frac12 & 0 & 0 & 0 & 0 & 0 \\
0 & d & -d+1 & -\frac12 & 0 & ...
- 323
3
votes
0
answers
243
views
An inequality concerning the solution of a Lyapunov equation
Let $A$ be an Hurwitz stable matrix (i.e. the real part of the eigenvalues of $A$ lie in the left-half plane) and $Q$ be a positive semidefinite matrix ($Q\ge 0$, for short). Let $P>0$ be the ...
- 2,712
0
votes
1
answer
540
views
Computing spectrum of convex combination of SPD matrices given individual spectral decompositions
Given the spectral decompositions of a non-commuting collection of symmetric positive definite $N\times N$ matrices $$\left\{ K_{i}\right\} _{i=1}^{M}, U_{i}D_{i}U_{i}^{T}=K_{i},\quad i=1,\dots,M,$$ ...
- 133
4
votes
1
answer
292
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
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
0
votes
1
answer
3k
views
Cholesky decomposition – non-positive definite matrix
In order to pass the Cholesky decomposition, I understand the matrix must be positive definite. However, I also see that there are issues sometimes when the eigenvalues become very small but negative ...
- 1
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
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