# Questions tagged [numerical-linear-algebra]

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

245
questions

1
vote

0
answers

63
views

### Find the eigenvectors from the QR algorithm in the unsymmetric case

It is possible to find many references describing the QR Algorithm with more or less refinements to approximate the eigenvalues of a square matrix $A\in\mathbb{R}^{n\times n}$.
I implemented a version ...

1
vote

0
answers

26
views

### Complexity of singular value decomposition using matrix multiplication oracles

Suppose I have an $n\times m$ real matrix $A$, $n\ll m$ with full row rank $(\mathrm{rank}(A) = n)$. I have an oracle that can compute $Ax$ or $A^T y$ for any $x\in \mathbb{R}^m, y\in \mathbb{R}^n$. ...

0
votes

1
answer

51
views

### What is the best way to choose initial basis when applying simplex method to an equality form of LP?

Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...

0
votes

1
answer

83
views

### Proving maximum value of a determinant of $I - B$, where $B$ is nonnegative matrix

I have the following setting:
Let $0 \leq r < 1$ and let $\{z_i\}_{i=1}^k$ be $k$ complex numbers such that $|z_i| \leq r$ for all $i$.
Moreover, $r + \sum_{i=1}^k 2Re(z_i) \geq 0$
I am interested ...

3
votes

2
answers

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

0
votes

1
answer

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

1
vote

1
answer

169
views

### Does Wilkinson's shift need to be discontinuous?

Given a symmetric Hessenberg matrix $A = \left[\begin{matrix}\ddots& \vdots & \vdots\\\dotsb & a & b\\\dotsb& b & c\end{matrix}\right]$, the Wilkinson shift $\mu$ employed in ...

2
votes

1
answer

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

2
votes

1
answer

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

0
votes

0
answers

17
views

### iterative linear solver with multiple starting vectors

Suppose I want to solve a (huge, sparse, self-adjoint) linear problem $Ax=b$ in a "matrix-free" form (i.e. without making components of $A$ explicit, just providing a function that computes $...

1
vote

0
answers

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

0
votes

0
answers

23
views

### Lanczos algorithm with a good initial vector

I want to find the smallest eigenvalue of a large, real, symmetric, sparse matrix. Suppose I have a good initial vector to start with. This initial vector is already close to the exact ground state (...

0
votes

0
answers

31
views

### Matrix decomposition to maximize square of sums rather than sum of squares like eigenvalues?

Matrix eigenvector decomposition finds the set of orthogonal vectors $\mathbf{v}_i$ that maximizes the L2 norms of those vectors $\mathbf{v}_i^\top\mathbf{v}_i=\lambda_i$, where $\lambda_i$ is an ...

2
votes

1
answer

70
views

### Where has the necessary and sufficient condition for the convergence of the unshifted QR algorithm been stated?

I've obtained a necessary and sufficient condition for the unshifted QR algorithm to converge. The condition for the algorithm to converge for a square matrix $M$ is:
For any two eigenvalues $\lambda$...

2
votes

0
answers

111
views

### Maximize the product of Hadamard matrix and a vector

Let $X$ be an $n \times n$ Hadamard matrix (i.e. entries are in $\{-1,1\}$ and rows are orthogonal). For my application, we can assume $n=2^k$.
Given a vector $\bf{w} \in R^n$, I want to find the $X^*$...

5
votes

2
answers

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

0
votes

0
answers

19
views

### piecewise linear system analysis with a switching boundary (plane)

Let's say there's a piecewise linear system having a switching plane as shown in the figure(line in this example).
And the initial condition of trajectory is given by a line segment $X_0$ at t=0.
$X_0$...

0
votes

0
answers

41
views

### Range of linear transformation of a natural vector

Given a natural variable vector and its upper bound $\vec{x}=[x_1,x_2,\dotsc, x_n]^\top,\vec{X}=[X_1,X_2,\dotsc,X_n]^\top$, where $x_i,X_i\in\mathbb{N}\wedge x_i<X_i,\ i=1,2,\dotsc,n$. With a ...

0
votes

0
answers

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

5
votes

1
answer

107
views

### Is Sun's spectral variation bound for normal matrices optimal?

In On the variation of the spectrum of a normal matrix, Sun proves the following result (Corollary 1.2):
Let $A$ be an $n$-square normal matrix and $B$ an arbitrary $n$-square matrix. Then $$ \min_{\...

0
votes

1
answer

110
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

0
answers

57
views

### Dense matrix vs sparse matrix, when they have same number of nonzero elements

I came across a new way in the literature to solve PDE problems numerically, which is called 'Patch Reconstruction'. One example paper is: Li, R., Sun, Z., Yang, F., & Yang, Z. (2019). A finite ...

3
votes

0
answers

123
views

### What is this SVD (called) with a singular value vector and U and V are tensors?

I am looking for information on a specific type of tensor/matrix decomposition which is quite similar to the SVD for matrices but does not look like the HOSVD since the core tensor is only a vector. ...

2
votes

1
answer

195
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

149
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

95
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

37
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

37
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

117
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

181
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

84
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

41
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

197
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

128
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

144
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

104
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

108
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

178
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

182
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

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

1
vote

1
answer

115
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

356
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

200
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

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

10
votes

2
answers

383
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

421
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

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

1
vote

0
answers

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

33
votes

3
answers

5k
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 an ...