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.
991
questions
1
vote
0answers
67 views
Solution of an underdetermined system stemming from a PDE with Neumann BC
Consider the Poisson's equation in 1D with homogeneous b.c.'s $\mathrm{d} \phi/\mathrm{d} x=0$ with the seven point Laplacian (1 -54 783 -1460 783 -54 1 / 576 on a uniform grid). The resulting system ...
2
votes
4answers
130 views
Eigenvalue decomposition for a very huge matrix of medical images (such as the pixel physical coordinates of CT images)
I am trying to do eigenvalue decomposition for a huge matrix larger than 788000×788000 for medical image analysis. The matrix is not sparse and every element in the matrix has a real value. And, for ...
4
votes
1answer
107 views
Solving geodesics on triangular meshes gives negative distances
I have implemented the heat method for geodesics:
https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/paperCACM.pdf
When I run it I am getting a solution that, visually, seems correct:
In this image, ...
3
votes
0answers
51 views
Check if LinearOperator is symmetric
I have a scipy.sparse.linalg.LinearOperator object. I'd like to check if its associated matrix is symmetric without actually instantiating the matrix in the most ...
3
votes
1answer
82 views
Lanczos algorithm for finding top eigenvalues of a matrix sum
I am trying to find the top k leading eigenvalues of a NumPy matrix (using python dot product notation) L@L + a*X@X.T, where $L$ ...
0
votes
0answers
89 views
Numerical Range of a matrix in Python
In the mathematical field of linear algebra and convex analysis, the numerical range or field of values of a complex
$n\times n$ matrix $A$ is the set
$$W(A)=\left\{{\frac {{\mathbf {x}}^{*}A{\...
2
votes
3answers
158 views
Linear solver recommendation(s) for small problems
I am interested in solving many linear systems $Ax = b$, where $A$ is symmetric positive definite and small (i.e. less than 25,000 rows) --- $b$ will be changing.
We can assume that $A$ arises from ...
2
votes
0answers
59 views
Software for solving large systems of linear equations over gf(2)
What available solvers are there for linear equation solver over GF(2) (Boolean), capable of dealing with large sparse systems (in the 10k - 100k variables range)?
-1
votes
1answer
32 views
Interpretation of error between Hessian approximation and real Hessian - Quasi-Newton Method
$$ ||I- H_{k}^{BFGS}\nabla^{2}f(x_{k})||_{2}$$
, where $H_{k}$ is the inverse of hessian approximation at each iteration.
I am given this expression to assess the error in Hessian approximation in ...
-2
votes
1answer
65 views
Forward Euler Adaptive Step Size Stability
Given
with a generalization using adaptive times-stepping as
then is it still reasonable to assume that to ensure stability of the Euler’s forward method we need the growth factor for all n to be ...
7
votes
3answers
433 views
Accurate Way to Calculate Matrix Powers and Matrix Exponential for Sparse Positive Semidefinite Matrices
I do need to numerically calculate the following forms for any $x\in\mathbb{R}^n$, possibly in python:
$x^T M^k x$, where $M\in\mathbb{R^{n\times n}}$ is a PSD sparse matrix, $n$ can be quite large ...
2
votes
0answers
42 views
How to solve this boundary value problem which has more unknown than equation on MATLAB
I need your helps about solving the problem below with MATLAB. I am trying to solve 2D Stress Wave Propagation problem by using FDTD(Finite difference time domain) method on the cylindrical coord. I ...
1
vote
2answers
119 views
Diagonalization using LAPACK
Say, we have a Hamiltonian which for simplicity does not mix particle hole sectors. It is just a simple Hamiltonian in real space as shown,
$H=\sum_{ij,\sigma} A(i,j)(c_{i\sigma}^{\dagger}c_{j\sigma} +...
0
votes
2answers
111 views
Given a symmetric matrix, is it ok to apply Cholesky decomposition to see if it has negative eigenvalues?
I intend to check the diagonal of L, where A = L'L, for negative elements. However, I don't know if Cholesky is meaningful in theoretical / computational sense if there are some negative eigenvalues.
0
votes
1answer
64 views
Solve for large array of PD matrices
I have N matrices that are positive definite, and I have to solve for a M vectors.
As M is large in my case, doing all solves simultaneously using np.linalg.solve ...
1
vote
1answer
51 views
Algebraic multigrid as solver and as preconditioner
My question is around the efficiency of AMG. In which case AMG can perform better,as solver or as a preconditioner(for example a Krylov space method as CG)? Assume the case of elliptic pdes.
2
votes
1answer
100 views
Efficiently compute a projection matrix from Householders reflectors
Let $A \in \mathbb{R}^{m \times n}$ where $m \geq n$.
Let $B$ and $\tau$ be the result of applying LAPACK's dgeqrfp method (R on the upper right triangle, and the ...
3
votes
1answer
117 views
A notion of resolution in inverse problems
Suppose I have a linear inverse problem of the form:
\begin{align}
Ax=b
\end{align}
I would like to reconstruct $x$ from the measurement $b$ via the objective
$$\min_x\{\vert\vert Ax-b\vert\vert^2_2+\...
1
vote
0answers
64 views
Upper bound on condition number in linear preconditioning
I'm studying iterative methods for solving linear system, and I find the following setting in Wikipedia:
Consider a matrix splitting $A = M-N$, where $A,M,N$ are all symmetric and positive definite ...
6
votes
1answer
216 views
Efficiently computing $e^{tX}$ for many different values of $t$
Given an anti-Hermitian and sparse matrix $X$, I am using Python (NumPy and SciPy) to compute the matrix exponential $f(t) := e^{tX}$ for many values of $t$. The method I am currently using is to ...
2
votes
1answer
105 views
Numerical Linear Algebra: When to use Direct methods versus iterative methods to solve a linear system - for PDEs in particular
I am reading the Chapra and Canale book on numerical methods, and was working through the chapters on solving linear systems. Now the book goes through direct methods including Gaussian Elimination, ...
1
vote
0answers
63 views
Given an unpivoted form of Aasen's algorithm, how does one add pivoting?
I've implemented the version of Aasen's algorithm described in the book Matrix Computations 4th Edition. The version there doesn't have pivoting. The book's description of how to add pivoting is a bit ...
2
votes
1answer
57 views
How do I extract the output of Aasen's algorithm into a usable form?
I tried implementing the algorithm in Aasen's 1971 paper on factorizing symmetric indefinite matrices. I've translated the code verbatim from Algol into Python, and I used the test example given in ...
1
vote
1answer
103 views
Complexity of solving an image differential linear system
Define an "image differential linear system" as a linear system $A\mathbf{x}=\mathbf{b}$ wherein $\mathbf{x}$ contains the ($\mathbb{R}$) pixels of an image and each row of $A$ constrains ...
6
votes
1answer
185 views
Parallelize Scipy iterative methods for linear equation systems(bicgstab) in Python
I need to solve linear equations system Ax = b, where A is a sparse CSR matrix with size 500 000 x 500 000. I'am using scipy.bicgstab and it takes almost 10min to solve this system on my PC and I need ...
5
votes
1answer
195 views
Symmetric matrix which satisfies conditions of the form $v_i^T X v_i = 0$
I want to solve an underdetermined system of linear equations $A x = b$ with $A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. The matrix $A$ has the following additional ...
0
votes
0answers
64 views
How to make a directed graph symmetric?
Say I have a directed graph given as an adjacency matrix $A$ in CSR format represented by the arrays ia (row indexes) and ja (...
3
votes
2answers
108 views
Equations that are easier to verify than to solve?
Are there interesting examples of (systems) of equations where it is known to be harder to find a solution (in terms of scaling with respect to problem size) than verifying a provided solution for ...
1
vote
1answer
95 views
Range of a matrix from its complete orthogonal decomposition
In this StackOverflow answer, @Gokul has shown how to get a basis of the kernel of a matrix with the help of the 'Eigen' function CompleteOrthogonalDecomposition. ...
1
vote
1answer
117 views
Factorization of cubic spline interpolation matrix
In cubic spline interpolation, we use the set of knots and function values $(x_i,y_i),i=1,...,n$ to construct a (tridiagonal) system of equations for the unknowns $\sigma_i$:
$$
h_{i-1}\sigma_{i-1} + ...
0
votes
0answers
48 views
Formula for overdetermined logical matrix pseudoinverse not requiring SVD?
In https://commons.wikimedia.org/wiki/File:YI_%3D_PI.png, you will find a formula-based solution for an overdetermined logical matrix pseudoinverse. This simple formula gives the same result as the ...
4
votes
1answer
85 views
Trace of inverse from LU decomposition
Given an LU decomposition of $A\in \mathbb{R}^{n\times n}$, is there a way to compute $\operatorname{trace}(A^{-1})$ with lower complexity than that of the inversion ($O(n^3)$ in practice)?
This ...
4
votes
0answers
54 views
Efficient computation of marginalized multivariate normal likelihood
In general,if we know that the marginal Gaussian distribution for some variable $\textbf{x}$ and a conditional Gaussian distribution for some $\textbf{y}|\textbf{x}$ of the forms:
$$p(\textbf{x}) = \...
3
votes
0answers
43 views
Choice of iterative solver for a sparse asymmetric matrix with symmetric structure
I have a sparse $nxn$ matrix A with pretty interesting structure. It has a block structure with symmetric structure but asymmetric blocks. Expressed mathematically $A_{jk} = A_{kj}$ but $A_{jk} \neq ...
2
votes
1answer
112 views
Diagonalization of Hermitian matrices vs Unitary matrices
What are the general algorithms used for diagonalization of large Hermitian matrices and Unitary matrices? ($>5000 \times 5000$)
LAPACK seems to diagonalize Hermitian matrices almost 20 times as ...
2
votes
0answers
83 views
Algorithm for computing inner products multiple times
I am taking a computational linear algebra course and i got stuck during a homework problem concerning the computation of inner products. I am supposed to compute the inner product:$$\mathrm{a}_{\...
4
votes
0answers
64 views
Optimize linear equation using inner products and subject to L1 norm
I have a linear system of the form $A x = b$ where $A$ and $b$ are known, $A$ is "square", and $\lvert b \rvert_1 = \lvert x \rvert_1 = 1$. Unfortunately, I am working in a framework that ...
2
votes
1answer
84 views
Efficient change of basis real positive definite symmetric matrix
I need to optimize a code where the most performance critical part is doing a 'change of basis', in other words it is an unitary similarity transformation on a big real positive definite symmetric ...
0
votes
0answers
70 views
Ill-conditioned stiffness matrix
I am writting a Fem code in c++ for a 2d plane stress model. My question is regarding the assembly stiffness matrix.I noticed that some elements of the matrix are not exactly zero but insted a number ...
1
vote
1answer
86 views
Jacobi iterative method
I'm using Jacobi iterative method for finding eigenvalue and eigenvector for hermitian or symmetric matrix. Eigenvectors corresponding to eigenvalues are not exact. The third eigenvector is totally ...
1
vote
0answers
25 views
Multiplying by E[xy'] where only some statistics of xy' are known
(cross-posted on crossvalidated)
For random variable $(x,y)$ in $\mathbb{R}^{d}\times \mathbb{R}^{d}$ and vector $v \in \mathbb{R}^d$, I need to perform the following matrix vector multiplication.
$$T(...
5
votes
0answers
132 views
Inverse problem with uncertain forward operator
Suppose I want to solve a linear inverse problem. In this example we take a convolution with the kernel:
$$\frac{1}{(y^2+z^2)^{3/2}}$$
We only take a fixed $z$ for the computation and convolve with ...
6
votes
2answers
263 views
When is it easy to invert a sparse matrix?
(Crossposted on cstheory.SE)
When is it easy to invert a sparse matrix? Specifically, I'm wondering about the cases in which matrix inversion has similar cost to sparse matrix multiplication, hence ...
2
votes
1answer
42 views
Solving MX=N where M is structured as a Gaussian 4th-moment tensor
I'm looking to solve numerically the following equation for $(d,d)$ variable $X$, in Einstein summation notation
$$M_{ijkl}X_{kl}=N_{ij}$$
Where $M$ is a $(d,d,d,d)$ 4th-moment tensor of random ...
2
votes
1answer
148 views
Ill-condioned Linear System and Gaussian Elimination
Suppose that I have a linear system $Ax=b$ such that $A$ is ill-conditioned. Can I say that it is dangerous to find a solution with Gaussian Elimination for this system, or does there exist some class ...
3
votes
2answers
191 views
1D FEM for nonlinear diffusion coefficient
I want to solve with linear finite elements the equation $$\partial_t u = \partial_{x}(a(u)\partial_xu)$$
in the domain $t \in [0,1]$ and $x \in [-L,L]$. Here $a(u)$ is just a function of $u$.
...
3
votes
1answer
99 views
Efficient solution to a structured symmetric linear system with condition number estimation
I have a real-valued linear system $Hx = b$ where $H$ is symmetric matrix** (not necessarily positive/negative definite) with a very particular structure:
$$
H = \begin{bmatrix} D && B \\ B^T &...
0
votes
0answers
47 views
Norm estimates if adjoints can't be computed
Assume that you have two linear maps $A$ and $V$. For a given $x$ (of appropriate dimension) you can compute $Ax$ numerically, and for any $y$ (of appropriate dimension) you can calculate $V^Ty$ ...
5
votes
1answer
690 views
Cheap recalculation of eigenvalues and eigenvectors for a low-rank update of the matrix
Suppose I have a correlation matrix, $A$, and I already have the eigenvalues and eigenvectors of this matrix.
For a given vector, $\mathbf{\mathit{v}}$, I want to calculate the eigenvalues and ...
2
votes
1answer
188 views
Runtime of Gaussian elimination/row reduction on a rectangular $m \times n$ matrix
The runtime of Gaussian elimination on an $n \times n$ matrix is $O(n^3)$. What is the runtime on an $m \times n$ matrix?
I am taking Gaussian elimination to mean putting the matrix in reduced row ...
