Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

4
votes
2answers
405 views

Solving Ax = b with sparse A and sparse b

Let's suppose I'm numerically solving the Poisson equation for a delta function source: $$ \nabla^2 f(x) = \delta(x-x') $$ I can represent the Laplacian $\nabla^2$ using the finite difference method ...
2
votes
1answer
325 views

Distributed (MPI) matrix matrix multiplication

I perform matrix matrix multiplications (between rank-3 and rank-2 arrays) in fortran using following subroutine, ...
4
votes
1answer
2k views

Block-matrix SVD and rank bounds

Assume, we have an $m\times n$ block matrix $M=\left[\begin{array}{c c}A&C\\B&D \end{array}\right]$, where $A$ is an $m_1 \times n_1$ matrix of rank $k_A$. $B$ is an $m_2 \times n_1$ matrix ...
1
vote
0answers
115 views

Eigenvalues using QR iteration

I'm trying find the eigenvalues of a matrix A using QR iteration with Householder. I used this code which I found from Cornell University that decomposes QR with Householder. ...
2
votes
2answers
63 views

Using low rank property for maximal/minimal value search (or sorting)

I was thinking about the following problem: Suppose there is a positive semidefinite matrix $X$ of size $n$ (for example, a kernel). Suppose $X$ can be approximated as a low rank matrix, $X\approx ...
1
vote
0answers
54 views

Reduce large sparse linear operators to memory efficient loops?

I'm dealing a lot with large sparse linear operators these days and I'm quite new to them. A lot of the matrices I deal with originate with only a few unique integers, however, there are lots of them. ...
7
votes
1answer
197 views

Does mean removal increase accuracy of numerical differentiation?

I wish to compute the derivative of a vector through numerical differentiation. Let's say, we use a standard 2nd order central difference scheme, to arrive at a differentiation matrix, and apply it on ...
3
votes
2answers
285 views

Precision loss in Matrix-Vector product when applying Finite-Difference scheme

I am applying a 6th order Finite-Difference differentiation scheme as seen in http://www.scholarpedia.org/article/Method_of_lines/example_implementation/dss006 There seems to be severe numerical/...
4
votes
1answer
199 views

SLEPc eigensolvers take long time to converge for large sparse symmetric matrices

I am leveraging the SLEPc library for solving the first $k$ (where $k = 3$ or $4$) eigenvalues and their corresponding vectors for a matrix of size 200,000. The matrix is sparse and symmetric. I ...
1
vote
1answer
223 views

Preconditioning ARPACK eigenvalue solver

I am working on a generalized eigenvalue problem of the form $$ \boldsymbol{A}\cdot\boldsymbol{x}=\lambda\boldsymbol{B}\cdot\boldsymbol{x} $$ where $\boldsymbol{B}$ is not symmetric positive. ...
0
votes
1answer
92 views

Writing a non-square linear system in standard form $A\cdot{x}=b$

I have spend the last few days working my way through an interesting paper and I'm building a numerical model so I can apply the method. However, I am getting stuck at an "it can be shown" step. I am ...
7
votes
3answers
2k views

Method to check for positive definite matrices

I think it's already been asked, but I still can't figure out a way to do it computationally. I had to check for positive definiteness of an $n \times n$ matrix $A$. I know that for any nonzero ...
5
votes
2answers
138 views

Compute $x = B^{-1}(2A+I)(C^{-1}+A)b$ without calculating matrix inverses

If $A, B, C$ are $n \times n$ matrices, where both $B$ and $C$ are nonsingular, and $b$ is a vector of length $n$, how would you compute the following without computing any inverses? $$x = B^{-1}(2A+...
1
vote
1answer
80 views

Eigenvalue problem constrained with a penalty method

I am trying to constrain an eigenvalue problem. I am aware of the method utilizing the nullspace of the constraint vectors but I was wondering if it would be to use a penalty method for the same ...
1
vote
2answers
2k views

BLAS libraries for Octave or Matlab, preferrably with GPU support?

I just searched around a bit for BLAS implementations and was amazed by the sheer amount of libraries around. Does someone know of a benchmark or otherwise rating of the various libraries? How easy ...
2
votes
0answers
159 views

Connectivity and Clustering using Eigenvectors and the Fiedler Vector

Going off of the answer here: sorting adjacency matrix by the Fiedler vector So here, Jesse the answerer plotted the first 3 eigenvectors associated with non-zero eigenvalues of the Laplacian against ...
2
votes
2answers
183 views

Comparison between two matrices

I have a large dense matrix $A$. For simplicity in simulation purposes and application demand, I induced sparsity by replacing lower/insignificant values by zero and reordering it in block diagonal ...
5
votes
0answers
229 views

How do I implement a working Lanczos biorthogonalization method for Krylov subspace?

I am trying to implement Lanczos biorthogonalization algorithm to construct a Krylov subspace basis. Given a matrix $A$, and vectors $v,w:(v,w)=1$, it produces three matrices $V,W,T$ such that $V^T W =...
1
vote
0answers
146 views

All eigenpairs of large sparse symmetric matrix

In advance I am sorry for my noobish question. I am a physics PHD student and basically I use python for my math/physics problems. But now I have a problem which requires more computing capacity and ...
7
votes
1answer
201 views

Numerically stable computation of the Characteristic Polynomial of a matrix for Cayley-Hamilton Theorem

I was wondering if there is any known way to compute the Charactaristic Polynomial P of a matrix A numerically stable in the sense of realizing the Cayley-Hamilton Theorem, i.e. that P(A)=0. I've ...
1
vote
2answers
410 views

Derivative of the inverse of the Right Cauchy-Green Deformation Tensor wrt itself

In continuum mechanics, we define the Right-Cauchy-Green Deformation Tensor as $\boldsymbol{C}=\boldsymbol{F}^T\boldsymbol{F}$ I want to compute $\frac{\partial \boldsymbol{C}^{-1}}{\partial \...
0
votes
3answers
1k views

What's the fastest implementation of elementwise vector multiplication in Fortran?

My fortran code contains lines like the following ...
4
votes
0answers
78 views

Computing Algebraic Riccati inequality

In my Robust model control, I have got a couple of quadratic Riccati inequalities which need to be solved numerically on MATLAB. My question, Is there function on MATLAB can solve quadratic Riccati ...
6
votes
2answers
209 views

Efficiently removing projection to subspace without having an orthogonal basis

I have a number of vectors $v_1, …, v_n$ and another vector $w$, that all are linearly independent, but not orthogonal. Let $V := \mathop{\text{span}}(v_1, …, v_n)$. I need to remove $w$’s projection ...
1
vote
0answers
83 views

QR via Householder: less computationally complex variants?

I'm a probabilist and need to do a few computations for a rather big linear least squares problem, so I'm trying to optimize the computation as far as is feasible to me. In computing the QR ...
0
votes
1answer
106 views

Role of non-hermitian coefficient matrices in the discretization of self-adjoint operators

What is the role of non-symmetric coefficient matrices in the solution of partial differential equations with self-adjoint operators? Particularly, I'm thinking about time-propagation of a linear ...
1
vote
0answers
47 views

Closed-form Jacobian of se3 element w.r.t. 6-dof motion

Let $A$ and $B$ be two rigid transformations in 3D space that transform things from global to local coordinates. Let their relative transformation be expressed by $W=A*B^{-1}$. $W$ can also be ...
1
vote
1answer
101 views

Finding the lowest $n$ eigenvalues of a band-diagonal Matrix

I have a real sparse matrix of the form $$ \left( \begin{array}{ccc} h_{11} & h_{12} & 0 & h_{14} & & & \\ h_{21} & h_{22} & h_{23} & 0 & h_{25} & & ...
1
vote
3answers
121 views

Solving a small non-symmetric, non-diagonally dominant, and non-sparse system

I want to solve a small (20 $\times$ 20 up to 30$\times$30) system which is not symmetric, not diagonally dominant, and not sparse. Each row contains a modified form of the Legendre coefficient of a ...
4
votes
0answers
142 views

Eigenvalues with absolute values close to 1

I have a generalized eigen-problem: $A\psi = \lambda B \psi$ with $A$ and $B$ are large (>1000) complex non-Hermitian matrices. I know that eigenvalues with largest and smallest absolute values can be ...
2
votes
0answers
135 views

Does applying the Newton-Raphson iteration for matrix reciprocal refine a matrix inverse from LU/GE?

This is a follow-up to this answer. Suppose you have a possibly very ill-conditioned matrix $A$, and you compute its inverse with LU/GE to get $X_{\text{lu}}\approx A^{-1}$. The Newton-Raphson ...
1
vote
1answer
136 views

What are the prominent algorithms for solving systems of linear inequalities?

Why, you may ask? The Python sympy symbolic library provides solutions to single, linear Diophantine equations in terms of parametric variables. For instance, ...
6
votes
3answers
673 views

Least Squares: Numerically, is solving normal equations okay for nice matrices?

I have to solve a least squares problem: $$ x=\arg \min\|Ax-b\| $$ where $A$ is a $m\times n$ matrix, $m>n$, and $b\in\mathbb{R}^m$. I always thought that doing this via QR factorization is ...
5
votes
2answers
515 views

Smart way to multiply 3 matrices

I have a quantum mechanics simulation where I need to multiply three matrices that look like this: $$\rho(t_1)=U^\dagger \rho(t_0) \, U$$ where $U^\dagger$ is the hermitian conjugate of $U$. This ...
1
vote
0answers
116 views

How to obtain projections from sinogram in ART reconstruction technique?

I'm kind new in the Computed Tomography field and I'm trying to understand and implement ART technique. Said it, I started to read the book The Mathematics of Medical Imaging - A Beginners Guide by ...
3
votes
2answers
915 views

Fastest way to perform element-wise multiplication on a sparse matrix

I have two large-ish matrices (~100K cols x ~100K rows). They are sparse and symmetrical (about 0.1% of them values are non-zero). I want to do element-wise multiplication between them. Also, I ...
0
votes
1answer
141 views

How to compute matrix representation of $\hat{y}\frac{\partial}{\partial x}$?

I have a 2-dimensional system which I would like to solve numerically (I'm using finite difference method right now), and its an eigenvalue problem. I have a term that looks like $H\psi(x,y) = [-\frac{...
4
votes
1answer
439 views

Thomas algorithm for 3D finite difference

For 1D finite difference, the resulting linear system is tri-diagonal and can be solved in O(n) using the Thomas algorithm. I am trying to solve a finite ...
4
votes
1answer
92 views

Compute specific eigenvalues in the complex plane with Feast?

In physical problems, it's quite common that we need to solve for specific eigenvalues in the complex plane, e.g. with a positive real part and negative imaginary part. In this case, we are looking ...
2
votes
0answers
48 views

Under what circumstances does Elemental's distributed SVD not work? [closed]

I am playing around with Elemental's distributed singular value decomposition and am running into two particular issues. Building the test at tests/lapack_like/SVD.cpp, and running with ...
1
vote
1answer
158 views

Appropriate Lapack/MKL routines to efficiently compute C = A* inv(B)

I know that, from numerical point of view, computing Ax = b B=inv(A), x= B*b are completely different things, and we should factor the matrix using TRF routine ...
11
votes
2answers
704 views

Compute all eigenvalues of a very big and very sparse adjacency matrix

I have two graphs with nearly n~100000 nodes each. In both graphs, each node is connected to exactly 3 other nodes so the adjacency matrix is symmetric and very sparse. The hard part is I need all ...
2
votes
1answer
57 views

Doubt regarding principled approach towards approximating the Hessian

In my optimization problem, the hessian has a structure such that it can be written as the sum of two matrices. Populating the first of the matrices is efficient. Populating the second one is ...
1
vote
0answers
58 views

What's the optimal method to solve for the top eigenvectors of a very large, real, symmetric matrix of limited rank?

Consider a real symmetric matrix of dimension N~10^5 and rank m~2000. What is the most efficient algorithm for determining the top m eigenvectors? If the answer isn't obvious, are there existing ...
9
votes
1answer
462 views

Matrix Balancing Algorithm

I have been writing a control system toolbox from scratch and purely in Python3 (shameless plug : harold ). From my past research, I have always complaints about ...
7
votes
1answer
345 views

Efficient algorithm for solving linear system with symmetric near-tridiagonal matrix?

I would like to solve the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$, with $$\mathbf{A}=\mathbf{T}+\mathbf{C}$$ where $\mathbf{T}$ is a symmetric tridiagonal matrix and $\mathbf{C}$ is a corner-...
2
votes
2answers
524 views

Compute all eigenvectors and eigenvalues of small symmetric matrices

My problem is to compute eigenvectors and eigenvalues of a lot of small (n < 30) symetric, positive definite matrices. So far I am using LAPACK's DSYEV. The priority is speed more than accuracy. ...
7
votes
1answer
144 views

Tikhonov (Ridge) Regression and Normalization

For a typical Ridge Regression method for solving an inverse problem $$ \min_x ||A~x - b||^2 + \lambda^2||\Gamma~x||^2 $$ Which has an analytical solution of $$ \hat{x}_{est}=(A^TA+\lambda^2 \Gamma^T\...
1
vote
0answers
52 views

bound error for iterative method for solving linear system

$A$ is square and positive definite, and let $r_k = Ax_k - b$. Also let $M = \frac{1}{2}(A+A^T)$. I want to show that $$\frac{||r_{k+1}||_2}{||r_k||_2} \le \left(1-\frac{\lambda_\min(M)^2}{\lambda_\...
3
votes
1answer
89 views

linear programming feasiblity checking

Is there any sufficient and necessary condition to check the feasibility of the linear constraints $Ax=b, x\geq 0$ without solving an LP with a constant objective function? $x$ is the variable and $...