Questions tagged [numerical-linear-algebra]

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

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5