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
5
votes
2answers
3k views

How to find the nearest/a near positive definite from a given matrix?

I'm given a matrix. How do I find the nearest (or a near) positive definite from it? The matrix can have complex eigenvalues, not be symmetric, etc. However, all its entries are real valued. The ...
3
votes
1answer
140 views

Is there any way/any python function to calculate the condition number of the roots of a polynomial directly?

I know that NumPy has linalg.cond(A) to find the condition number of a matrix A. But, if I want to find the condition numbers of the roots of a large polynomial ...
1
vote
1answer
72 views

Can someone explain the equivalence between Oja's rule and PCA in a simple way?

I have to give a presentation on unsupervised learning in 2 days, and I have to explain/show the equivalence between Hebb's learning rule (or Oja's rule to be more specific) and PCA. The thing is that ...
5
votes
3answers
340 views

Why do structured and unstructured discretizations give different errors?

It is necessary for me to solve a Poisson problem with a numerical method on a square domain with two types of triangular mesh: uniform triangular mesh (using uniform distribution nodes on square) and ...
2
votes
0answers
90 views

Regularisation of ill-conditioned matrix-vector problem

I have a linear* problem which arises from an integro-differential system, and writes: $$ (\mathbf{I}+\lambda \mathbf{A})x = b $$ where $\mathbf{A}$ is a real full matrix, size $n\times n$, but is not ...
4
votes
0answers
102 views

PETSc-like library for Julia

I want to build an application for Material Point Method (and probably other meshfree methods too) in Julia and I am looking for library for direct and iterative solvers that can help me with it. One ...
3
votes
1answer
81 views

Find $x$ that satisfy $(I-A^*A)+x(\frac{A+A^*}{2})\prec0$ using LMI or SDP on Matlab

Given $A\in\mathbb{C}^{n\times n}$, I want to use LMI or SDP to find feasibility of $x>0$ in the following inequality: $$(I-A^*A)+x(\frac{A+A^*}{2})\prec0,$$ where $D\prec0$ means that $D$ is ...
5
votes
2answers
469 views

Computational method to compute both the (log) determinant and inverse of a matrix

Suppose I have a square matrix $\mathbf{A} \in \mathbb{R}^{n\times n}$ and a vector $\mathbf{b}\in\mathbb{R}^n$. In my application I need to accomplish two things. I need to find the solution of the ...
4
votes
1answer
102 views

Solving for a single element of a solution of a linear system

I wish to solve a linear system $A x =b$ in which $A$ is dense but not too large, say no larger than $10\times10$. However, I am not interested in the full solution vector $x = [x_0, x_1, \dots]$, ...
2
votes
0answers
61 views

Multigrid method: linear solver and modified residual

I am trying to better understand the FAS multigrid algorithm for Euler equation in FV discretization. The usage of the modified residual (the residual with forcing) inside the different cases: ...
3
votes
0answers
86 views

Stable iterative solver for complex symmetric linear systems

I am interested in the iterative solution (preferably Krylov-type solvers) of a problem Ax=b, with x, b ∈ ℂn x 1 and A ∈ ℂn x n. A is symmetric, invertible, and its real and imaginary parts are ...
3
votes
1answer
106 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 the block $A_{jk} = A_{kj}$ but $A_{...
5
votes
2answers
105 views

Optimizing a quadratic form integral over unit sphere

I have an optimization problem, which is to maximize the following integral over the unit sphere: $$ \max_B \int d\Omega \mathbf{f}^{\dagger}(\theta,\phi) (B^{\dagger} + B) \mathbf{f}(\theta,\phi) $$ ...
0
votes
2answers
119 views

Implementation of $[X, \cdot]$ as an $n^2 \times n^2$ matrix, where $X$ is an $n \times n$ matrix

Let $M_n(\mathbb{R})$ denote the set of $n\times n$ matrices with real entries. I have an $n\times n$ matrix $X\in M_n(\mathbb{R})$, and I would like to implement the linear operator $[X, \cdot] : M_n(...
0
votes
0answers
60 views

Comparing minimas of two different functions

The goal is to find vectors $x_u$ and $y_i$, both of the same length $f=64$, and to do this the following loss function is minimized: $$\sum_{u, i} (1 + \alpha \cdot r_{ui})(p_{ui} - x_{u}^{T}y_i)^2$$ ...
6
votes
1answer
192 views

Algorithm for solving systems which are nearly symmetric/adjoint?

I am familiar with Cholesky decomposition and LU factorization for solving systems of linear equations. I have a problem where I have large sparse matrices (say, 1000x1000 or larger) where only one or ...
5
votes
2answers
196 views

Term for the typical "linear in the larger dimension, quadratic in the smaller" cost for linear algebra

Many dense linear algebra decompositions (QR, SVD...) on an $m\times n$ matrix have cost $$ O(\max(m,n)\min(m,n)^2) $$ when implemented in practice on a computer. Is there a colloquial name or a more ...
33
votes
6answers
29k views

What is the fastest way to calculate the largest eigenvalue of a general matrix?

EDIT: I am testing if any eigenvalues have a magnitude of one or greater. I need to find the largest absolute eigenvalue of a large sparse, non-symmetric matrix. I have been using R's ...
18
votes
4answers
2k views

Why do we usually not want the eigenvalues of non-symmetric matrices?

I came across this line in a class note I am reading where it discusses finding eigenvalues of matrices. In reality we don't go all the way with Arnoldi. We stop at a decent value of 𝑘. Then the 𝑘 ...
5
votes
1answer
133 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. \...
13
votes
5answers
482 views

Rapidly determining whether or not a dense matrix is of low rank

In a software project that I'm working on, certain computations are vastly easier for dense low-rank matrices. Some problem instances involve dense low-rank matrices, but they're given to me in full, ...
1
vote
1answer
95 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
85 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
51 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/...
7
votes
3answers
367 views

Is LAPACK behind the cutting edge of dense linear algebra?

I have been digging into some numerical linear algebra lately, and reading in particular about how LAPACK solves symmetric eigenvalue problems. I noticed that the ...
0
votes
0answers
136 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 ...
2
votes
2answers
535 views

Solution of the linear system using Sherman-Morrison formula for 1000000x1000000 (7450.6GB) matrix using MATLAB

Let $n = 10^6.$ Let $A \in \mathbb{R}^{n\times n} $ be the lower triangular matrix having 1's on and below the main diagonal. We want to solve the following linear system: $$ (A + uv^T)x = b$$ by the ...
3
votes
3answers
193 views

Fast iterative approximate order-oblivious Orthogonalization algorithm?

I have set of N m-dimensional vectors $\{\phi_i\}$ which gradually loses mutual orthogonality in an algorithm. => I have to re-orthogonalize them every few iterations. But if I use the Gram–Schmidt ...
3
votes
2answers
423 views

MA57 vs HSL_MA57: symmetric indefinite solvers

What are the differences between MA57 and HSL_MA57 solvers? I'm in an optimization class that will make use of symmetric indefinite factorizations, and I'm trying to learn about the distinction ...
3
votes
1answer
132 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
49 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
81 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
54 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
97 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
75 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 ...
6
votes
4answers
2k views

Efficient eigen-decomposition of covariance matrix

I am looking for an C/C++/Python algorithm implementation that calculates eigenvalues and eigenvectors of a symmetric, positive semidefinite covariance matrix. A general-purpose eigen-decomposition ...
2
votes
4answers
183 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
115 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
1answer
108 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$ ...
3
votes
0answers
66 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 ...
0
votes
0answers
180 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{\...
14
votes
3answers
2k views

Why is my parallel solver slower than my sequential solver?

I was playing around with PETSc and noticed that when I run my program with more than one process via MPI it seems to run even slower! How can I check to see what is going on?
2
votes
3answers
161 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
1answer
474 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 ...
2
votes
0answers
60 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
34 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
77 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 ...
4
votes
2answers
3k views

A numerical GMRES example

I'm having trouble understanding how GMRES works. I've read the part in Saad's book and a few others but still I am confused. Can someone provide me a numerical example to understand it better? Or if ...
13
votes
1answer
1k views

How is Krylov-accelerated Multigrid (using MG as a preconditioner) motivated?

Multigrid (MG) may be used to solve a linear system $Ax=b$ by constructing an initial guess $x_0$ and repeating the following for $i=0,1..$ until convergence: Compute the residual $r_i = b-Ax_i$ ...
8
votes
3answers
607 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 ...

1
2 3 4 5
21