# 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,154 questions
Filter by
Sorted by
Tagged with
133 views
+50

### What's the most computationally efficient implementation of Kalman Filter

I know there are many formulations of the Kalman Filter. A few I can name are: Classical Covariance Form Informational Filter Form Square-Root Form or Factor Form But somehow it's hard for me to ...
• 425
78 views

• 35
83 views

### Getting singular matrices for lid driven cavity problem

I was trying to solve the lid driven cavity problem using the galerkin method with SUPG stabilization. I was using GMRES method as my solver and I am also getting a solution. And the solution looks ...
1 vote
53 views

### Particular linear systems: sparse matrix + column

I am trying to understand a limitation in a routine in the interval arithmetic software Intlab. From matrices starting from a given size (in my particular problems),...
• 1,077
92 views

### An alternative to Levenberg–Marquardt algorithm

When trying to solve for a (over)determined non-linear least square method: $$\underset{x}{\min}||f(x)||^2_2, f: \mathbb{R}^n \rightarrow \mathbb{R}^m, x\in \mathbb{R}^n, m\geq n$$ we use the Gauss-...
1 vote
117 views

### On the calculation of the first m generalized eigenvectors

This is a classic generalized eigenvalue/eigenvector problem: $$A\,\vec{x}=\lambda\,B\,\vec{x}$$ which, however, is characterized by: $A,B$ are real, symmetric and positive definite matrices of ...
• 113
154 views

### Optimized Lanczos method for finding eigenvalues of $A \otimes B$

Recently my supervisor told me about an efficient way to calculate eigenvalues and eigenvectors of matrix $A \otimes B$ with $a_{1} \times a_{2}$ as dimensions of $A$ and $b_{1} \times b_{2}$ is of $B$...
142 views

### Products of the Householder matrices during QR decomposition

It is often said that there is no need to form the Householder matrix during QR decomposition, however I fail to see how to "manage" the product of $n$ Householder matrixes and the matrix $A$...
• 317
204 views

### Matrix Diagonalization and Computational Requirements

I have some questions about diagonalizing matrices. My interest lies in computing all eigenvalues of a given matrix. To avoid wasting time and improve my research efficiency, I want to understand the ...
• 133
64 views

### Is AMG supposed to work with discontinuous Galerkin discretizations?

As the question says, are algebraic multigrid methods well suited to be used as preconditioners for problems discretised with Discontinuous Galerkin methods (say $p=1$)? I've always used AMG (actually,...
• 405
110 views

### Is there a fast matrix-free inverse power iteration?

Problem: I want to solve the eigenvalue problem $$x=Ax$$ to the eigenvalue $1$ for a large matrix (roughly $N^3\times N^3$ and $N$ ranges from 10 to 100) where $A$ is stochastic (i.e. all entries are ...
935 views

### How to efficiently compute the determinant of a matrix with unknown diagonal entries?

I would like to ask Python to compute the determinant of a large symmetric matrix where all off diagonal entries are known. The diagonal entries could vary. Since I need to compute the determinant ...
81 views

### Computing the Fiedler vector of a large, sparse graph

I have a sparse, undirected and unweighted graph $G$ of size $n$, with $n$ on the order of say several million. I would like to compute the Fiedler vector $f$ of $G$, which is the eigenvector ...
• 503
40 views

### Flexible Conjugate Residual

If we want to use variable preconditioning in Conjugate Gradient, we can replace the Fletcher–Reeves by the Polak–Ribière formula (https://en.wikipedia.org/wiki/Conjugate_gradient_method#...
• 21
161 views

### Numerically stable computation of $x^T A x$

We have a large sparse symmetric positive-definite matrix $A \in \mathbb R^{N \times N}$ and a vector $x \in \mathbb R^N$. How do I practically compute the inner product $x^T A x$ when the matrix $A$ ...
• 3,680
1 vote
73 views

### Fill-reducing ordering for computing the matrix product $A^T A$?

I have found many libraries for reducing filling when dong Cholesky factorisation on sparse matrices. However, I want to do fill-reduction for a different reason - given a $m\times n$ matrix $A,$ I ...
• 161
70 views

### Weird runtime behavior of scipy.linalg.solve_triangular and trtrs

I want to understand the time complexity of scipy.linalg.solve_triangular, which calls trtrs from LAPACK under the hood, so I ...
• 181
1 vote
107 views

### How to implement boundary conditions for the Thomas algorithm

For my variable $U(t,x)$, I have implemented the thomas algorithm with $U_j^i$: $$a(x)U_{j-1}^{i+1}+ b(x)U_j^{i+1} + c(x)U_{j+1}^{i+1} = d(x)U_j^{i}$$ Then $\textbf{A}$ is a tridiagonal vector with ...
75 views

### Best transform of matrix to make it efficient for shift-then-invert?

I am using ARPACK to find the smallest eigenvalue of a matrix. I use the shift and invert method. That is, looking for the largest eigenvalue of $$(A-\sigma I)^{-1}.$$ However, I do not know $\sigma$...
• 161
192 views

### Why for $A^T A$, it is faster to computer the eigenvalues of its inverse than itself?

I have written the following code in MATLAB. I also observe the same effect in Arnoldi iteration in ARPACK in C. ...
• 161
94 views

### Computing smallest singular value of a matrix with explicit error control?

[Also posted here: https://mathoverflow.net/q/464433/] Many good algorithms are out there computing truncated SVD: https://mathoverflow.net/q/161252. I am trying to implement some codes to find the ...
• 161
1 vote
82 views

### Ways to speed up Lanczos algorithm when we have a very dense cluster of many eigenvalues?

Lanczos algorithm can be used to find the largest/smallest eigenvalues of matrices. I am trying to find a good library in C/C++/Rust for finding the smallest singular value (or eigenvalue). I have ...
• 161
1 vote
92 views

### Efficient projection onto the kernel of a matrix

Suppose I have a positive semidefinite matrix $M = \sum_i^N A_i^T A_i$ where each $A_i$ is a fat matrix of shape (m,n) and $m << n$, we can also assume that $A_i$ is full rank(but the stacked ...
• 113
3k views

### Real-world applications of eigendecomposition?

Cross-posted on Math.SE Are there real-world applications that call specifically for eigenvalues rather than singular values? I often see eigendecomposition used as "poor-man's SVD" For ...
• 2,675
24 views

• 185
59 views

1 vote
99 views

### enough conditions to check that a matrix doesn't have Cholesky factorization while factorizing it

I wrote this code to find Cholesky factorization of a symmetric positive definite matrix in MatLab: ...
118 views

• 263
133 views

### Numerical continuation of all eigenvalues of small, dense matrices

Consider a one-parameter family of matrices $A(q)\in \mathbb{R}^{n\times n}$, $q\in\mathbb{R}$. For my applications, $n$ is typically between $5$ and $50$ and $A(q)$ is generally dense, so direct ...
• 2,706