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,142 questions
Filter by
Sorted by
Tagged with
88 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 ...
35k views

How does the MATLAB backslash operator solve $Ax=b$ for square matrices?

I was comparing a few of my codes to "stock" MATLAB codes. I am surprised at the results. I ran a sample code (Sparse Matrix) ...
211 views

Estimating the spectral radius when applying the method of lines

Some time integrators, notably the Runge-Kutta-Chebyshev method, implemented in the RKC code from Sommeijer & Verwer, gives the user an option to provide a callback with an estimate of the ...
897 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 ...
150 views

Numerical calculation of the Berry connection

I'm doing some numerical calculations involving Hermitian matrices, and derivatives of the eigenvectors. Essentially, I have an n x n, Hermitian matrix H(x), which is dependent on some continuous ...
70 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 ...
31 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#...
152 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$ ...
1 vote
68 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 ...
67 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 ...
1 vote
91 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 ...
67 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$...
189 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. ...
92 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 ...
1 vote
71 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 ...
1 vote
89 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 ...
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 ...
60 views

Help with inferring Network topology from Spectral templates

I am trying to use matlab and YALMIP to solve a graph learning problem of recovering eigenvalues from the eigenvectors of the covariance of sampled graph signal data. This is to implement the ...
579 views

$\mathbf{UDU}^\top$ decomposition routines in LAPACK/Eigen?

I would like to compute the decomposition of a real symmetric positive definite matrix $\mathbf{A} = \mathbf{UDU}^\top$. LINPACK seems to have it as DSIFA, but I ...
179 views

60 views

Singular Matrix Error in Incomplete LU Decomposition

I’m currently working on solving the following PDE: $$$$-(\mu_x \frac{\partial^2 u}{\partial x^2} + \mu_y \frac{\partial^2 u}{\partial y^2}) = f(x, y)$$$$ Where a right hand ...
116 views

Name for vectors in a Krylov space but not the preceding one

It seems to me that a useful concept to define when studying Krylov subspace methods is the idea of a vector $v$ that belongs to a Krylov subspace $\mathcal{K}_{n+1}(A,b)$ but not to the preceding one ...
59 views

18 views

1k views

CHOLMOD condition number estimate

The CHOLMOD library provides a CHOLMOD_rcond function that estimates the reciprocal condition number (in the one norm) of a symmetric positive definite matrix from ...
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.
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 ...
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 ...
I'm solving $Ax = b$ with PETSc, $A$ sparse and asymmetric. I'm using BCGS or FGMRES or TFQMR as a solver, and ILU as a preconditioner. When I use 1 core, everything works as expected. But with 8 ...
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 ...