# Questions tagged [numerical-linear-algebra]

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

245 questions
Filter by
Sorted by
Tagged with
1 vote
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
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$. ...
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 ...
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 ...
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 &...
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
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 ...
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 ...
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 ...
17 views

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

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

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