Questions tagged [numerical-linear-algebra]

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

Filter by
Sorted by
Tagged with
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 ...
user avatar
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$. ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 59
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 &...
user avatar
  • 65
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 ...
user avatar
  • 21
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 ...
user avatar
  • 3,321
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 ...
user avatar
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 ...
user avatar
  • 677
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 $...
user avatar
  • 131
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, ...
user avatar
  • 677
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 (...
user avatar
  • 265
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 ...
user avatar
  • 1
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$...
user avatar
  • 3,321
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^*$...
user avatar
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 ...
user avatar
  • 542
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$...
user avatar
  • 19
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 ...
user avatar
  • 1
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{...
user avatar
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_{\...
user avatar
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{\...
user avatar
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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
  • 121
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 ...
user avatar
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 ...
user avatar
  • 163
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 \...
user avatar
  • 31
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 ...
user avatar
  • 241
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 ...
user avatar
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_{...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 2,475
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} ...
user avatar
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 &...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 21
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\...
user avatar
  • 13
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 ...
user avatar
  • 2,475
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 ...
user avatar
  • 3,321
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 ...
user avatar
  • 3,321
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) ...
user avatar
  • 31
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 ...
user avatar
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 $...
user avatar
  • 185
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 111
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 ...
user avatar
  • 325
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 ...
user avatar
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 ...
user avatar
  • 3,321

1
2 3 4 5