# Questions tagged [linear-algebra]

Questions on the algorithmic/computational aspects of linear algebra, including the solution of linear systems, least squares problems, eigenproblems, and other such matters.

1,124 questions
Filter by
Sorted by
Tagged with
214 views

### Efficiently compute a projection matrix from Householders reflectors

Let $A \in \mathbb{R}^{m \times n}$ where $m \geq n$. Let $B$ and $\tau$ be the result of applying LAPACK's dgeqrfp method (R on the upper right triangle, and the ...
215 views

• 544
66 views

### Formula for overdetermined logical matrix pseudoinverse not requiring SVD?

In https://commons.wikimedia.org/wiki/File:YI_%3D_PI.png, you will find a formula-based solution for an overdetermined logical matrix pseudoinverse. This simple formula gives the same result as the ...
• 101
173 views

### Trace of inverse from LU decomposition

Given an LU decomposition of $A\in \mathbb{R}^{n\times n}$, is there a way to compute $\operatorname{trace}(A^{-1})$ with lower complexity than that of the inversion ($O(n^3)$ in practice)? This ...
• 11.1k
74 views

• 121
76 views

### Optimize linear equation using inner products and subject to L1 norm

I have a linear system of the form $A x = b$ where $A$ and $b$ are known, $A$ is "square", and $\lvert b \rvert_1 = \lvert x \rvert_1 = 1$. Unfortunately, I am working in a framework that ...
• 245
163 views

### Efficient change of basis real positive definite symmetric matrix

I need to optimize a code where the most performance critical part is doing a 'change of basis', in other words it is an unitary similarity transformation on a big real positive definite symmetric ...
222 views

### Ill-conditioned stiffness matrix

I am writting a Fem code in c++ for a 2d plane stress model. My question is regarding the assembly stiffness matrix.I noticed that some elements of the matrix are not exactly zero but insted a number ...
• 481
1 vote
157 views

### Jacobi iterative method

I'm using Jacobi iterative method for finding eigenvalue and eigenvector for hermitian or symmetric matrix. Eigenvectors corresponding to eigenvalues are not exact. The third eigenvector is totally ...
1 vote
26 views

• 792
49 views

### Norm estimates if adjoints can't be computed

Assume that you have two linear maps $A$ and $V$. For a given $x$ (of appropriate dimension) you can compute $Ax$ numerically, and for any $y$ (of appropriate dimension) you can calculate $V^Ty$ ...
• 1,738
1k views

### Cheap recalculation of eigenvalues and eigenvectors for a low-rank update of the matrix

Suppose I have a correlation matrix, $A$, and I already have the eigenvalues and eigenvectors of this matrix. For a given vector, $\mathbf{\mathit{v}}$, I want to calculate the eigenvalues and ...
• 189
3k views

### Runtime of Gaussian elimination/row reduction on a rectangular $m \times n$ matrix

The runtime of Gaussian elimination on an $n \times n$ matrix is $O(n^3)$. What is the runtime on an $m \times n$ matrix? I am taking Gaussian elimination to mean putting the matrix in reduced row ...
• 23
1 vote
205 views

### Frobenius norm of a binary matrix

In term of the mathematical distance measurement, What is the significance of a Frobenius norm for a binary matrix?
1 vote
472 views

### How to optimize nuclear norm subject to positive semidefinite constraints?

For finite dimensional symmetric positive semidefinite matrices $A$ and $B$, I would like to solve \begin{align}&\min |X - A|_1 \\ &\text{subject to}\\ &X \preceq B \\ &0 \preceq X\...
• 113
84 views

### Derivative-free ill-conditioned non-linear least squares

I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as ...
• 131
865 views

198 views

### Accurately Computing a Positive Vector in the Nullspace of a Matrix

I'm sure this question has been asked before yet after many hours of searching I am unable to find a definitive answer. The problem at hand is solving the linear system: $$A \mathbf{x} = \mathbf{0}$$ ...
• 53
332 views

### A parallelized GMRES solver?

My application calls for solving a dense, 40,000 x 40,000, ill-conditioned linear system. The native SciPy GMRES solver with preconditioning has worked well for my application and solving a single ...
126 views

### Why is LAPACK (seemingly) suboptimal for packed and banded eigenvalue problems?

Based on this LAPACK routines list, it looks like there is no relatively robust representation (RRR) driver routine for either packed or banded symmetric eigenvalue problems. According to the relevant ...
• 201