Skip to main content

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.

Filter by
Sorted by
Tagged with
9 votes
0 answers
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 ...
CuriousMind's user avatar
0 votes
1 answer
78 views

optimize this python code that involves matrix inversion

So I have this line of code that involves a matrix inversion X = A @ B @ np.linalg.pinv(S) $A$ is an $n$ by $n$ matrix, $B$ is an $n$ by $m$ matrix and $S$ is an $...
Taylor Fang's user avatar
4 votes
1 answer
99 views

How can I efficiently find an anti-symmetric generator of a special orthogonal matrix?

Given a special orthogonal matrix $O$ (i.e: $OO^T = 1$ and $\det(O) = 1$), I am trying to efficiently find a matrix $X$ such that $O = e^X$ and $X = -X^T$ using Python (NumPy & SciPy). One obvious ...
Solarflare0's user avatar
2 votes
0 answers
83 views

What is fastest method for finding the minimum and maximum eigenvalues of a (possibly very large) symmetric matrix?

What is the best way to find the extreme eigenvalues - in order to find the spectral radius - of a general real dense symmetric matrix? Looking at similar questions e.g.: What's the most efficient ...
ufghd34's user avatar
  • 21
1 vote
1 answer
191 views

Solving linear system of equations with constraints on unknowns

I would like to solve a system of linear equations $y=Uh$ for an unknown vector $h$, where I have a few constraints on some of the elements of $h$. The matrix $U$ is composed of a vector $u$ (length $...
Neuling's user avatar
  • 35
2 votes
2 answers
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 ...
Priyanshu's user avatar
1 vote
0 answers
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),...
Beni Bogosel's user avatar
  • 1,077
2 votes
0 answers
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-...
William Lin's user avatar
1 vote
1 answer
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 ...
Monster's user avatar
  • 113
5 votes
2 answers
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$...
Mohammad. Reza. Moghtader's user avatar
4 votes
1 answer
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$...
Olumide's user avatar
  • 317
3 votes
1 answer
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 ...
yosuga's user avatar
  • 133
3 votes
0 answers
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,...
FEGirl's user avatar
  • 405
0 votes
0 answers
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 ...
Diplodokus's user avatar
10 votes
5 answers
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 ...
dangqingdouna's user avatar
2 votes
1 answer
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 ...
Set's user avatar
  • 503
0 votes
0 answers
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#...
GS101's user avatar
  • 21
4 votes
1 answer
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$ ...
shuhalo's user avatar
  • 3,680
1 vote
1 answer
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 ...
Ma Joad's user avatar
  • 161
0 votes
1 answer
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 ...
nalzok's user avatar
  • 181
1 vote
0 answers
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 ...
THATS MY QUANT MY QUANTITATIVE's user avatar
0 votes
0 answers
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$...
Ma Joad's user avatar
  • 161
4 votes
0 answers
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. ...
Ma Joad's user avatar
  • 161
0 votes
0 answers
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 ...
Ma Joad's user avatar
  • 161
1 vote
0 answers
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 ...
Ma Joad's user avatar
  • 161
1 vote
2 answers
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 ...
HRI's user avatar
  • 113
13 votes
8 answers
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 ...
Yaroslav Bulatov's user avatar
0 votes
0 answers
24 views

dual svm square hinge loss

Let $x_1,\dots,x_n\in \mathbb{R}^n$, $y_1,\dots,y_n\in \{-1,1\}$, $\lambda \ge 0$ and $K$ be the invertible Gram matrix $K=(x_i\cdot x_j)_{ij}$. Consider $$ (P) \qquad \qquad \min_{a\in \mathbb{R}^n} \...
Smilia's user avatar
  • 478
0 votes
0 answers
72 views

Singular Matrix Error in Incomplete LU Decomposition

I’m currently working on solving the following PDE: $$\begin{equation} -(\mu_x \frac{\partial^2 u}{\partial x^2} + \mu_y \frac{\partial^2 u}{\partial y^2}) = f(x, y)\end{equation}$$ Where a right hand ...
blov's user avatar
  • 43
3 votes
2 answers
191 views

what preconditioner for incompressible hyperelasticity in 3d (similar to stokes equation?)?

I am working on modeling incompressible elasticity at finite strains. $$ \mathrm{Div} \boldsymbol P = \boldsymbol 0, \quad \boldsymbol X \in \Omega_0 \subset \mathbb R^3, \\ J = 1, \qquad \boldsymbol ...
Simon's user avatar
  • 185
0 votes
0 answers
59 views

Solving AU = F using linalg.cg results in 0 iterations

I am working on solving the following PDE: $$\left(\mu_{x}\frac{\partial^{2}u}{\partial x^{2}}+\mu_{y}\frac{\partial^{2}u}{\partial y^{2}}\right)=f(x,y) \tag 1$$ Which is then discretised: $$- \mu_{x} ...
blov's user avatar
  • 43
1 vote
1 answer
92 views

accuracy problem for a null space calculation on a sparse rectangular matrix

I have been using the QR-based approach on this link to find the null space of rectangular matrices, and possibly sparse matrices, that emerge as a result of some coupling conditions of different ...
Umut Tabak's user avatar
0 votes
0 answers
61 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 ...
user86422's user avatar
1 vote
1 answer
89 views

Are there any established direct eigensolvers for sparse hermitian matrices?

I have experience with LAPACK (direct solvers) and ARPACK (sparse iterative solvers), but are there any sparse direct solvers? I am concerned more with preserving space than with fast solutions. ...
DJames's user avatar
  • 417
0 votes
1 answer
117 views

Finding the Vector $v$ for a Given Householder Matrix Transformation of Non-Collinear Vectors $a$ and $b$

Consider a vector $v$ in $\mathbb{R}^{n\times1}$. The Householder matrix is defined as follows: $$H(v)=I-\dfrac{2vv^T}{v^Tv}.$$ It can be demonstrated that $H(v)$ is symmetric and orthonormal. The ...
Ferran Gonzalez's user avatar
2 votes
0 answers
44 views

How to use a preconditioner estimated from a subset of data?

Suppose I'm solving $Ax=b$ using row-action method like Kaczmarz for $m\times n$ matrix A with $m\approx \infty$ and have $H_k=\frac{1}{k}A_k^T A_k$ which is an estimate of the Hessian obtained from ...
Yaroslav Bulatov's user avatar
3 votes
1 answer
188 views

Solving underdetermined Lyapunov equation?

I'm solving the following for $X$ with $A,B$ singular positive semidefinite matrices. $$AX + XA = B$$ Because $A$, $B$ are singular, standard Lyapunov solver fails However, if I heuristically skip ...
Yaroslav Bulatov's user avatar
0 votes
0 answers
20 views

How do you determine the Mott-Insulator to Superfluid transition in the Bose Hubbard System

I am doing some simulations on various systems expressed in 2nd quantization and one of the points of interest of mine was Phase transitions in the Bose-Hubbard model $$ H = \sum_{k} \{ t_k(b^\dagger_{...
Mephistopheles Faust's user avatar
1 vote
1 answer
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: ...
Ferran Gonzalez's user avatar
3 votes
0 answers
118 views

Stochastic power iteration for generalized eigenvalue problems?

Suppose $\mathbf{x}$ is a random variable in $n$ dimensions, and $u$ is a vector. How can I estimate the following quantity in an online fashion? $$f(x)=\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\...
Yaroslav Bulatov's user avatar
1 vote
1 answer
70 views

Dyadic product of a Gaussian vector (in Convolution kernel)

I was reading about the 2D Gaussian-blur convolution kernel. A Gaussian vector is a vector where the elements follow a Gaussian distribution. In my case, the kernel is symmetric and hence we take a ...
SKPS's user avatar
  • 171
12 votes
2 answers
2k views

Why are systems with clustered eigenvalues easy to solve?

I came across the following slide by Theo Diamandis & Zachary Frangella on what makes the linear system $Ax=b$ easy to solve using the conjugate gradient method. Transcription: CG converges ...
Yaroslav Bulatov's user avatar
0 votes
1 answer
202 views

Problems on the algebraic theory of sparse matrices

I have finished testing basic large densely parallel matrix multiplication on 4 gpu's ,and have done work on TSLU and TSQR on cpu's based on mpi. I am going to continue working on the theory of ...
Haitao Xiao's user avatar
4 votes
1 answer
352 views

How to efficient solve $e^{-tA} x =b$, where A is a very sparse matrix

I am going to solve an equation containing an exponential matrix $e^{tA} x =b$, which can be obtained naturally through $x=e^{-tA} b$. A is a 1million $\times$ 1 million matrix with stores 7.15 ...
Owen Jun's user avatar
  • 141
0 votes
1 answer
289 views

Questions on the theory of distributed numerical algebraic computation

I'm trying to build a pure python distributed numerical algebra computation kernel based on GPU. but after I've learnt most of the software engineering, I realise that I'm seriously lacking in ...
Haitao Xiao's user avatar
4 votes
1 answer
215 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 ...
IPribec's user avatar
  • 617
0 votes
0 answers
48 views

recommendation on some papers/books about frontal solver used in FEM

I'm reading a program about computational plasticity, this program use frontal solver to solve the program, but I'm not familiar with frontal solver even after reading some papaers, so could you ...
吴yuer's user avatar
  • 193
0 votes
1 answer
49 views

How do you build a polyharmonic discrete system?

Polyharmonic equations, to my understanding, are defined as: $$\Delta ^k u = 0$$ i.e. one repeatedly applies the laplace operator to the function a certain number of times and the result must be 0. ...
Makogan's user avatar
  • 263
5 votes
1 answer
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 ...
whpowell96's user avatar
  • 2,706
0 votes
1 answer
98 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 ...
Makogan's user avatar
  • 263

1
2 3 4 5
24