# Questions tagged [numerical-linear-algebra]

{numerical-linear-algebra} questions involving algorithms for linear algebra computations.

226
questions

**2**

votes

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**3**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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 ...