# 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,149 questions
Filter by
Sorted by
Tagged with
51 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
49 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
1 vote
81 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
108 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
110 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$...
138 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
177 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
62 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
108 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 ...
921 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 ...
77 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
39 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
158 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,670
1 vote
71 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
68 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
106 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 ...
73 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
190 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
93 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
77 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
91 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,665
23 views

• 165
59 views

1 vote
97 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: ...
116 views

• 263
120 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,636
96 views

### Computing discrete laplacian matrix for mesh fairing

I asked this question on the math stack exchange and got an answer, but I am just as utterly confused as before. My fundamental goal is to actually construct the matrix, that is, a series of steps I ...
• 263
9k views

### stupid + stupid = brilliant in scientific computing

I'm interested in examples of very effective methods in scientific computing that are the sum or naive combination of very ineffective or bad ones.
• 10.3k
47 views

### Different computational approaches to show that the conjecture is true

It seems that proving the statement given in the question https://math.stackexchange.com/questions/4601532/a-pen-and-paper-proof-for-a-matrix-implication is difficult analytically. I was thinking what ...
• 229
1k views

### Why are all eigen solvers iterative?

I have small dense square matrices for which I would like to compute the inverse by singular value decomposition, or equivalently solve the eigenvalue problem. While there are many direct methods for ...
• 2,375
Given a bivariate polynomial system with variables $(x, y, z)$ like (1) $f_1 = x * a_1 + y * a_2 + z * a_3 = 0$ (2) $f_2 = x * a_4 + y * a_5 + z * a_6 = 0$ (3) $f_3 = x^2 + y^2 - 1 = 0$ how do I ...
A number of numerical problems are easy to solve when condition number $\kappa$ of the problem is low. For instance, conjugate gradient descent complexity scales as $O(\sqrt{\kappa})$. However "...