# Questions tagged [numerical-linear-algebra]

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

226 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
24 views

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

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