Questions tagged [numerical-linear-algebra]
{numerical-linear-algebra} questions involving algorithms for linear algebra computations.
226
questions
2
votes
1answer
41 views
Derivative of eigenvalues of a symmetric tridiagonal matrix built via the Lanczos-Arnoldi scheme
Suppose $\mathbf{A}(\mu)$ being a symmetric positive definite matrix of dimension $n$ where its elements depend parametrically on the real parameter $\mu$.
Suppose now to build the orthonormal basis ...
2
votes
1answer
141 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 ...
0
votes
1answer
70 views
Is there a specific name for this optimization problem?
Let $A$ be an $n\times n$ symmetric positive definite matrix with eigenvalues and eigenvectors $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n>0$ and $v_1,v_2,\cdots,v_n$ respectively.
We know that the ...
1
vote
0answers
24 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 \...
2
votes
0answers
33 views
Transforming a symmetric matrix into pentadiagonal form
Given a symmetric matrix $A$, which has complex values in the diagonal, but whose all other entries are real, I am interested in finding an orthonormal transformation $Q$ such that $Q^tAQ$ is a ...
1
vote
0answers
85 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 ...
3
votes
2answers
151 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
1answer
34 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 ...
0
votes
0answers
30 views
Numerically finding matrix approximation by lower-dimensional “pseudo-similar” matrix
Consider an $N\times N$ (real or complex) matrix $A$, and some $n<N$. Is there a good numerical algorithm that finds the set consisting of an $n\times n$ matrix $B$, an $n\times N$ matrix $I$, and ...
3
votes
1answer
68 views
Condition number for matrix of eigenvectors of a diagonalizable matrix
Let $A$ be a diagonalizable matrix, i.e., $A=SDS^{−1}$. For any matrix $A$, condition number is defined as $\kappa(A)=\|A\| \|A\|^{-1}$.
For $A$ being a diagonalizable matrix, define $G_A=\{{S: S^{-1} ...
0
votes
1answer
75 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 &...
6
votes
1answer
58 views
What is the big-O complexity of solving the sparse Laplace equation in the plane?
In MATLAB, you can get a 2d Laplacian via A = delsq(numgrid('S',N)); yielding a matrix $A$ that is $n \times n$ with $n = O(N^2)$, for a square domain discretized ...
2
votes
1answer
168 views
How to solve this set of equations as efficiently as possible. Efficiently measured in FLOPS
The system of equations is the following:
$$
\Gamma_i^{\ -1} = \sum_{i=1}^nA_{ij}\Gamma_j,
$$
where $\Gamma = (\Gamma_i)$ is a vector of size $n$ and $A$ is a matrix of size $n\times n$, with $n \gt ...
1
vote
1answer
87 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\...
7
votes
0answers
100 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 ...
3
votes
1answer
169 views
Does there exist an O(n^3) algorithm for deciding whether PAP^T = LDU is solvable given some square matrix A?
Let $A$ be an arbitrary real square matrix. Does there exist an $\mathcal O(n^3)$ algorithm for deciding whether there exists a permutation matrix $P$, lower unit triangular matrix $L$, upper unit ...
1
vote
1answer
94 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 ...
2
votes
2answers
54 views
Solution to a matrix optimisation problem with a particular structure
Does a matrix of the form $A_{ij} = v_i + v_j$ for some arbitrary vector $v$ have a particular name?
I am attempting to find the closed form solution (if it exists, although it looks like it might) ...
0
votes
0answers
31 views
Relating spectral guarantee to L2 guarantees
Let $A \in \mathbb{R}^{d\times d}$ be a real, symmetric matrix. Let $U_k \in \mathbb{R}^{d\times k}$ denote the matrix containing the first top $k$-components (eigenvectors) $u_i$ of $A$ as its ...
0
votes
0answers
29 views
Numerically solving the optimization problem $\min \| x \|_{\ell^1} \ s.t. \ \| Ax-b \|_{\ell^2} \leq \delta$
Consider a linear system $Ax=b$ with matrix $A$ and right hand side $b$ and suppose one is interested in a sparse solution of this system. In the situation where the right hand side is corrupted by ...
1
vote
1answer
108 views
Complexity of solving $\sum_i A_i X B_i = C$
Is anything known about computational complexity of finding $X$ which satisfies the following matrix equation?
$$\sum_i^n A_i X B_i = C$$
With $A_i,B_i,C$ dense $d\times d$ matrices. Any literature ...
9
votes
1answer
334 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 $...
6
votes
1answer
191 views
Computing $(AA\otimes BB + AB \otimes BA)^{-1}$
Can anyone suggest a way to numerically compute the following matrix vector product?
$$u=A^{-1}b=(AA\otimes BB + AB \otimes BA)^{-1}\operatorname{vec}(C)$$
Here $AA,BB,AB,BA$ and $C$ are $d\times d$ ...
1
vote
0answers
66 views
Approximating matrix multiplication with integer arithmetic
The following question is inspired with approximation of matrix multiplication computations occurring in numerical simulations and machine learning algorithms with a use of efficient integer ...
8
votes
2answers
200 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 ...
9
votes
1answer
310 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 ...
2
votes
0answers
89 views
block diagonal approximation of (SPD) matrix
I am interested in approximating a symmetric matrix in a block diagonal form, i.e. compute just some entries of the matrix located in blocks around the diagonal. Are there any theoretical guarantees ...
0
votes
0answers
56 views
A question about implementation of Farkas lemma
The Farkas Lemma: Let $A$ be an $m\times n$ matrix, $b\in\mathcal{R}^m$. Then exactly one of the following two assertions is true:
(1) There exists an $x\in \mathcal{R}^n$ such that $Ax=b$ and $x\ge0$...
1
vote
0answers
102 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 ...
27
votes
3answers
4k 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 TTE.
Assume that there is an algorithm that, given a symmetric real matrix $M$, finds real ...
0
votes
1answer
95 views
Best-approximation with tensors of rank $\ge2$
Let $k\in\mathbb N$, $H_i$ be a (finite-dimensional, if necessary) $\mathbb R$-Hilbert space for $i\in I:=\{1,\ldots,k\}$, $H:=\bigotimes_{i\in I}H_i$ denote the tensor product$^1$ of $(H_i)_{i\in I}$ ...
1
vote
0answers
57 views
Fast computation of linear equation with row and column removed
Given $A, x, b$ and a linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ is full rank. Denote $A_{\backslash i}$ as a $(n-1)\times(n-1)$ matrix where $A$ removes its $i^{th}$ column and row, ...
0
votes
1answer
126 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{...
0
votes
0answers
32 views
How to adjust two Gramian matrices to make them “aligned” without enumeration?
I have two set of vectors:
V1,V2,V3,...,Vn
W1,W2,W3,...,Wn
And two Gramian matrices of them: Mv, Mw
Now I want to find an ordering of W1,W2,W3,...,Wn such that the Gramian matrix of the new order of ...
3
votes
2answers
102 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 ...
1
vote
0answers
26 views
Compute Frobenius inner product of two tensor-trains in terms of tensor contractions
Let $p\in\mathbb N$, $n\in\mathbb N^p$ and identify the Hilbert space tensor $\bigotimes_{k=1}^p\mathbb R^{n_k}$ with $\mathbb R^{n_1\times\cdots\times n_p}$ (equipped with the Euclidean inner product)...
1
vote
0answers
15 views
Show that a tensor-train is contained in a recursive sequence of subspaces
Let
$p\in\mathbb N$;
$n_k\in\mathbb N$ and $\left(e^{(k)}_1,\ldots,e^{(k)}_{n_k}\right)$ denote the standard basis of $\mathbb R^{n_k}$ for $k\in\{1,\ldots,p\}$;
$u\in\bigotimes_{k=1}^p\mathbb R^{n_k}...
0
votes
0answers
31 views
Most efficient way to solve against large sparse matrix with a few dense rows and columns?
I have a constrained optimization problem of the form:
$$
\min_{Bx=g} \frac{1}{2} x^T A x - x^T f
$$
$A \in \mathbb{R}^{n\times n}$ is positive semi-definite (with a tiny null space of dimension &...
1
vote
1answer
71 views
How can I find minimum and maximum eigenvalue of non-positive define matrix [closed]
There is a power iteration method, but it only returns the greatest(in absolute value) eigenvalue of matrix. So when we have negative eigenvalues it'll give wrong results.
Is there any method, which ...
0
votes
0answers
68 views
How to solve a non-local self-consistent equation
I have been struggling lately with solving numerically an equation of the form:
$$ g(x\pm x_{0}) = F[ g(x) ] $$
where $g(x)$ is a matrix satisfying the condition $g(x\to\pm\infty)=0$. My question is ...
1
vote
0answers
16 views
One-sided Jacobi SVD and Divide&Conquer SVD stability and cost [closed]
I'm studying SVD, in particularly the Jacobi SVD and Divide&Conquer SVD algorithms. I can't find anything on the stability and error analysis on these methods. Also can someone show show me what's ...
0
votes
0answers
29 views
ADMM for solving linear systems
I would like to use ADMM for solving $Mx=b$, where $M\in \mathbb{R}^{R\times R}$ is symmetric and positive definite. I know that a lot of methods will do for me in this case, but I'm specially ...
3
votes
1answer
95 views
How to find the elliptical arc that corresponds to the cubic bezier curve
Let's assume I have a cubic bezier curve that is provided with A, B, C, D points, where
A is the start of the curve
B is the first control point
C is the second control point
D is the end of the ...
0
votes
0answers
36 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 ...
6
votes
1answer
107 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 ...
7
votes
1answer
180 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 ...
8
votes
2answers
226 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 ...
2
votes
1answer
56 views
Matrix factorization for dimensional reduction similar to spectral decomposition/SVD
I have a graph clustering problem I'm working on and it basically involves finding a factorization of the adjacency matrix $A$ such that the following equations are (approximately) satisfied:
$$
A \...
1
vote
1answer
179 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 ...
2
votes
1answer
159 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 ...
