As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [numerical-linear-algebra]

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

278 questions
Filter by
Sorted by
Tagged with
81 views

### Substitution vs elimination in solving system of linear equations [closed]

I believe that elimination is generally the preferred method to solve a system of linear equations compared with substitution. To be precise, by substitution method on a system of linear equations, it ...
1 vote
48 views

### Characterization of the behavior of the residuals in conjugate gradient

In conjugate gradient method for solving symmetric positive definite linear system $Ax=b$, which can also be regarded as a convex optimization problem $\dfrac{1}{2} x'Ax - x'b$, the $A$-norm of the ...
1 vote
39 views

### QR algorithm for eigenvalues and eigenvectors of large symmetric matrices

I am trying to write a QR algorithm in Python for eigenvectors and eigenvalues finding for large symmetric matrices, My initial thought was to use Householder transformation with a Wilkinson shift ...
2k views

### Quickly determining if a matrix has any PSD completion

Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion? Slightly more precisely: for simplicity let's assume ...
78 views

96 views

### Complexity of inverting and multiplying against a symmetric Toeplitz matrix with two repeated entries

I know that the computational complexity of inverting a general $n \times n$ matrix $A$ is $O(n^{2.373})$ and multiplying it against an $n \times m$ matrix is $O(n^2m)$. Moreover, I've seen that ...
32 views

### The backward error of tridiagonal linear system $Ax=b$ by Gaussian elimination without pivoting

Let $A$ be an $n \times n$ nonsingular tridiagonal matrix having an $LU$ factorization. It can be shown that the computed solution of the linear system $Ax = b$ using Gaussian elimination without ...
1 vote
12 views

### Optimal Truncation of LDL-factorization to improve conditioning

Suppose I factored real symmetric quasi-definite $A_0= L_0 \cdot D_0 \cdot L_0^T$ and the factorization exists, with $D$ diagonal and $L$ unit lower-triangular; and suppose $L$ and $D$ are badly ...
1 vote
30 views

### Slope assertion in Cholesky on digital computers

For a real symmetric positive definite linear system $$A \cdot x = b,$$ solved using Choelsky with forward- and backward-substitution, we know it for the numerical approximation $\tilde{x}$ to $x$ ...
106 views

### Practical symmetric equivalent to QR factorization updates

As we know, the QR-factorization $Q\cdot R=A$ of any real symmetric $n \times n$ matrix $A$ with full rank is unconditionally numerically stable. Further, when A is rank-1-updated, the factorization ...
383 views

68 views

### $\det(HH’) = 0$ for nonnegative $H$

$H$ is an $n\times m$ matrix with non-negative coefficients and $n < m$. $H'$ is the transpose of $H$. Are the following statements true? If $\det(HH’) > 0$, the rows of $H$ define the edges of ...
17 views

### Identifying redundant vectors In non-negative matrix bases

I have a target non-negative matrix $X$ that I would like to factor. I have two non-negative matrices $W$ and $H$ such that $WH = X$. In this formulation, the rows of $H$ are $L^2$ normalized and ...
1 vote
57 views

5k views

### Why is fast matrix multiplication impractical?

I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication. I read some content saying fast matrix multiplications are impractical because of large ...
1 vote
154 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
110 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$. ...
97 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 ...
107 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 ...
713 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 &...
140 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
183 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 ...
130 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 ...
248 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 ...
103 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, ...
77 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$...
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^*$...
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 ...