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
1 vote
1 answer
43 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
58 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
72 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 ...
THAT'S MY QUANT MY QUANTITATIV's user avatar
0 votes
0 answers
15 views

Affine point matching in general dimensions [migrated]

Fix a positive integer $d$ and consider the $d$-dimensional Euclidean space $\mathbb{R}^d$. Let $S$ and $T$ finite subsets of $\mathbb{R}^d$ of the same size $n$. Under the assumption that $S$ and $T$ ...
rr314's user avatar
  • 101
0 votes
0 answers
64 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
178 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
89 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
68 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
88 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
22 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
  • 468
0 votes
0 answers
52 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
176 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
  • 165
0 votes
0 answers
58 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
84 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
59 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
87 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
58 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
42 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
186 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
18 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
87 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
113 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
66 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
199 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
319 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
  • 131
0 votes
1 answer
285 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
3 votes
1 answer
145 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
  • 597
0 votes
0 answers
46 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
  • 173
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
4 votes
1 answer
105 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,259
0 votes
1 answer
92 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
38 votes
10 answers
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.
Daniel Shapero's user avatar
0 votes
0 answers
46 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 ...
BAYMAX's user avatar
  • 229
4 votes
1 answer
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 ...
Aurelius's user avatar
  • 2,365
0 votes
1 answer
67 views

Solve bivariate polynomial system

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 ...
Citizen3011's user avatar
8 votes
0 answers
291 views

Stable alternatives to "condition number"?

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 "...
Yaroslav Bulatov's user avatar
3 votes
1 answer
56 views

Matrices that achieve worst-case $LDL^T$ element growth

Matrices that achieve the worst case $\rho_n = 2^{n-1}$ element growth in LU factorization with partial pivoting are known; see e.g. Theorem 9.7 in Higham, Nicholas J., Accuracy and stability of ...
Federico Poloni's user avatar
0 votes
0 answers
54 views

How do compute lowest eigenvalue using Arpack in C language

Hi I have a problem to calculate lowest eigenvalue in non-symmetric matrix using Arpack, because my matrix is very complicated and even I have a lot of trouble to made a matrix - vector multiplication....
Maciej Lewkowicz's user avatar
1 vote
0 answers
35 views

How to find the formula of a projected circle in a pencil of conics structure?

Hi this is my first question on the platform so feel free to comment if I have a mistake regarding the question. I'm working on an ellipse detection scheme in which I have markers consisted of 3 ...
kemal alperen cetiner's user avatar
5 votes
1 answer
136 views

Estimating the sum of 4th powers of singular values?

Suppose $A$ is an $m\times n$ matrix with $\operatorname{Tr}(AA^T)=1$. Let $\sigma_i$ be the vector of singular values of $A$. How would I cheaply estimate the following quantity? $$\rho(A)=\sum_i \...
Yaroslav Bulatov's user avatar
3 votes
0 answers
156 views

When would one choose un-pivoted $LDL^T$ instead of $LL^T$ for a Positive Definite Matrix?

Background I am decomposing (and then operating on) a symmetric positive definite matrix (a covariance matrix) as part of a larger system. Dimensions range from O(10) to O(300). The covariance ...
Damien's user avatar
  • 802
1 vote
0 answers
84 views

Optimal Krylov subspace dimension and iteration limits for eigs

When using the eigs function in MATLAB, which is based off of ARPACK, one can manually modify the maximal dimension of the constructed Krylov subspaces, the maximum iteration counts, and the error ...
user45844's user avatar
2 votes
1 answer
115 views

Tools to compare two matrices with same dimensions

Context: I have two 3D non-random matrices that have the same dimensions. These matrices represent satellite images with 1 band, so their values are strictly positive. They both present areas that ...
Nihilum's user avatar
  • 121
1 vote
0 answers
65 views

min(f(x)) is convex or concave based on type of f(x)

i have f(x) that is concave function. My question is g=min(f(x)) is concave or convex? And max(g) is concave or convex? there is a theorem for this?
Maria's user avatar
  • 11
2 votes
1 answer
170 views

Measuring the extent to which two sets of vectors span the same space

I have a set of measurements $y_i$, $1 \leq i \leq N$, and I want to model these measurements with a linear model. I have two possible models I can use, $$ y \approx A c $$ and $$ y \approx B d $$ ...
vibe's user avatar
  • 1,048
3 votes
1 answer
226 views

Generalized eigenvalue problem for large, potentially ill-conditioned systems

Say that I have a generalized eigenvalue problem of the form $$Ax=\lambda Bx.$$ Using MATLAB, some naive ways that one may solve this is by either directly inverting $B$ then applying the ...
user45844's user avatar
1 vote
0 answers
64 views

How to show that the solution of the following quadratic programming is non-negative

I have the following quadratic problem: $max$ $a^Tx+0.5x^TAx$ $s.t: 1^Tx=1$ in which $a=[a_1, a_2,...,a_n]$ is a non-negative vector, and $1^T=[1,1, ..., 1]$. The hessian matrix $A$ has the ...
user45682's user avatar
11 votes
1 answer
1k views

Is using iterative methods to solve a linear system always superior to inversing the matrix?

I have a silly question. Is it always more computationally efficient to use iterative methods to solve for some matrix $A$, $Ax=b$, where $x$ and $b$ change but $A$ stays constant, compared to ...
Touko Puro's user avatar

1
2 3 4 5
23