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
votes
0answers
34 views

Python approach for calculating a 2D matrix by interpolating 'between' two other 2D histograms [closed]

I have two 2D histograms, A and B, calculated from simulations by changing a single input parameter (alpha and beta set at "5" and "7", respectively). I want to calculate a third ...
5
votes
1answer
102 views

Solving absolute value systems

Let $z, b \in \mathbb R^n$, $A \in M_n (\mathbb R)$ and $|z| := (|z_1|, \dots, |z_n|)$. I am searching for an efficient algorithm to solve the absolute value system: \begin{equation} z - A |z| = b. \...
1
vote
1answer
42 views

Efficiency of scipy.sparse.linalg.expm_multiply with sparse vs unsparse vectors

From the package scipy.sparse.linalg in Python, calling expm_multiply(X, v) allows you to compute the vector ...
1
vote
0answers
82 views

Matlab - Equality between 2 Fisher matrices constructed in a different way

I want to know if, on a Fisher matrix, the projection operation (with a Jacobian matrix) commutes with a matricial inversion operation. The 2 ways to build these 2 matrices are: 1) First method: 1.1) ...
0
votes
0answers
47 views

PLASMA usage (Linear algebra routines that supports multithreading)

I have been looking for linear algebra libraries that support multithreading. I have found PLASMA which looks promising. It is from the same group that developed LAPACK. http://icl.cs.utk.edu/...
0
votes
0answers
134 views

Do the projection (with Jacobian) and marginalisation (inversion of matrix and remove a row/column and reinversion) commute?

I try to check the equality or the inequality between 2 Fisher matrices. The goal is too see if the projection (with Jacobian) and marginalisation (inversion of matrix and remove a row/column and ...
3
votes
1answer
89 views

How can I extract the banded or block diagonal part of a sparse matrix in MATLAB?

Given a large sparse (square) matrix in MATLAB, how can I extract the banded or the block-diagonal parts (of fixed size) of it efficiently? These are useful operations when prototyping and testing ...
0
votes
1answer
41 views

Efficient solution to linear system involving Kronecker sum in MATLAB

High dimensional finite difference problems often lead to linear systems of the form $$ A x = b, \qquad A = B_1 \oplus B_2 \oplus \cdots \oplus B_d, $$ where $\oplus$ denotes the Kronecker sum. $B_i \...
4
votes
0answers
78 views

Unstable Algorithms which become stable when hardware provides Kulisch exact dot product instruction

In John Gustaffson's book The End of Error, he discusses Ulrich Kulisch's exact dot product, which (in double precision) requires a 2100 bit fixed point register which rounds only once after the ...
1
vote
0answers
51 views

Number of words that a processor can handle for PMMM

The PMMM which stands for parallel matrix-matrix multiplication essentially accelerates the algorithm of the matrix-matrix multiplication of two matrices $A$ and $B$ both of size $n$ so that $C:= AB$. ...
3
votes
0answers
65 views

Jacobian Matrix of 2D element mapped to 3D

Note: I previously posted this question to MathStackExchange, but got no attention there. So I'm rewritting and trying over here. Problem summary Given a common¹ set of shape functions defined at ...
1
vote
0answers
74 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
148 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
110 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
57 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
95 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
109 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
33 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
74 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 ...
8
votes
3answers
527 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
144 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
117 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
68 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
56 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
111 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
127 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
68 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
236 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
111 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
116 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
226 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
197 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
66 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
108 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
130 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
90 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
58 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
45 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
132 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
84 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
66 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
93 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
83 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
2 3 4 5
21