Questions tagged [matrix]

Matrix is a rectangular array of elements (e.q. numbers, symbols, or expressions), arranged in columns and rows.

Filter by
Sorted by
Tagged with
8
votes
0answers
350 views

Updating matrix diagonal with Woodbury matrix identity and maintaining numerical accuracy

I have a dense matrix A and its corresponding inverse $A^{-1}$. The Woodbury matrix identity states: $$ (A + UCV)^{-1} = A^{-1} - A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1} $$ I wish to perform small ...
7
votes
3answers
8k views

Gershgorin Circle Theorem to estimate the eigenvalues

In order to estimate the eigenvalues of a real symmetric $n\times n$ matrix, I intend to use the Gershgorin Circle Theorem. Unfortunately, the examples one might find on the internet are a bit ...
7
votes
3answers
365 views

Does a symmetric positive definite matrix also have $\mathbf{A} = \mathbf{L}^T\mathbf{L}$ (where $\mathbf{L}$ is a lower triangular matrix)?

As we know, for a symmetric positive definite (SPD) matrix $\mathbf{A}$, there is a theorem about the Cholesky factorization $\mathbf{A}= \mathbf{L}\mathbf{L}^T$, where $\mathbf{L}$ is a lower ...
7
votes
3answers
245 views

Wanting to learn about matrix solvers

Edit: I was advised to replace the question with a more specific one. Coming from a very theoretical background, I'm pretty ignorant about what practical matrix solvers exist. (I have been, and will ...
7
votes
3answers
2k views

What is the criteria for switching between Strassen's and Regular matrix multiplication Algorithms

Strassen’s Matrix Multiplication algorithm has theoretical performance of $ O( n^{log_2 7}) $. Regular MM algorithm has performance of $ O( n^{3}) $. At certain sizes of matrices (lets call it $n*n$),...
7
votes
3answers
2k views

How to compute the rank of a large sparse matrix in MATLAB

I am interested in computing the ranks of fairly large, the largest being of magnitude $10^6$ x $10^6$, sparse matrices whose entires are all 0, 1, or -1. I have been trying to use Matlab to ...
7
votes
2answers
484 views

Is large condition number good measure of nearness to singularity for a matrix?

I am new to numerical linear algebra, so i came to know that condition number in 2-norm case will be ratio of largest to smallest singular value. Another concept "Nearness To Singularity" is measured ...
7
votes
1answer
302 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 ...
7
votes
1answer
405 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-...
7
votes
2answers
179 views

Lanczos algorithms for Hermitian system with Toeplitz kernel

Basically, I am trying to compute the SVD of a large Hermitian matrix $H$ using Lanczos iteration, while $H$ consists if a Toeplitz kernel $K$, which should be able to help speed up the matrix-vector ...
7
votes
1answer
80 views

Bad scaling versus collinearity

I was trying to solve a linear system: $$ \mathbf{A}\mathbf{x} = \mathbf{y} $$ but the conditioning number was quite bad (around $10^{17}$). I thought that the system was singular, but after scaling ...
7
votes
1answer
349 views

Least-squares for a diagonal matrix

This is a follow-up to a different question I asked with more detail. For $v\in\mathbb{R}^n$, denote $D_v\in\mathbb{R}^n$ as the diagonal matrix with elements in $v$. Given a "tall" matrix $B\in\...
7
votes
1answer
221 views

Compute eigenvectors of a matrix with known eigenvalue spectrum

If I have already accurately known the eigenvalue spectrum (i.e. all eigenvalues) of a matrix, is there any efficient numerical algorithm to compute all the eigenvectors corresponding to these ...
7
votes
1answer
585 views

Jacobi iteration to reduce the quadratic function

Given certain function $f(X)$ which is quadratic in $X\in\mathbb{R}^{n\times d}$, $$\frac{1}{2}tr(X^TAX) - tr(Y^TBX)$$ for positive definite weighted Laplacian matrices $A, B\in\mathbb{R}^{n\times n}...
7
votes
1answer
873 views

Sparse hermitian eigensystems: are there better techniques than Arpack or TRLan?

As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
7
votes
0answers
278 views

Speed and accuracy of Strassen vs Winograd matrix multiplication algorithms

I am doing work which requires as fast matrix multiplication as possible and just want to double-check with this community that the Winograd variant of Strassen's MM algorithm is the fastest practical ...
7
votes
0answers
274 views

Eigenvalue with largest imaginary part

Iterative eigensolvers such as ARPACK, give the option to find a subset of the eigenvalues which have the largest imaginary part. My question is how do these algorithms work. As I understand it, ...
6
votes
2answers
707 views

Matrix multiplication accuracy Matlab vs Python

I am translating some Matlab code into Python and I having some problems regarding matrix multiplication accuracy. Assuming we have following data: ...
6
votes
3answers
1k views

Eigenvectors with the Power Iteration

To compute the eigenvector corresponding to dominant eigenvalue of a symmetric matrix $A\in\mathbb{R}^{n\times n}$, one used Power Iteration, i.e., given some random initialization, $u_1\in\mathbb{R}^...
6
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 ...
6
votes
2answers
330 views

How important is the exponential of a matrix in computational science?

CS people: The title is the question, as I will explain. As everyone reading this probably knows, if $A$ is a square matrix of real or complex numbers, then $e^A$, or $\exp(A)$, is the matrix of the ...
6
votes
2answers
109 views

Approximating the exponent of a matrix $\exp(A)$ using Taylor series

I am trying to approximate the exponential of a matrix. I want to use a tolerance but I am confused as to how to compute the error. Any ideas or hints?
6
votes
2answers
321 views

What guidelines should I use when choosing a scalable linear solver?

There are many different linear solvers, some which work best for diagonally dominant matrices, some for symmetric, some for positive definite ones, some for banded matrices, etc... There are direct ...
6
votes
2answers
271 views

Derive PCA with SVD

The context is I have a big matrix, 20K * 50K, and I want reduce the dimensionality. In R, it's impossible to apply PCA with more variables(columns) than observations(rows). Therefore, I am trying a ...
6
votes
1answer
257 views

Eigenvector with maximum overlap

Given a matrix $M$ and a vector $v$, is there an efficient method to find the normalized eigenvector of $M$ that is closest to $v$, in that it has maximal overlap. More explicitly, a vector $v$ can be ...
6
votes
2answers
2k views

Computing the pseudoinverse of a 3x3 matrix

I need to compute the (Moore-Penrose) pseudoinverse of fixed-size 3x3 matrices. I would prefer to have a simple method without bringing in the industrial strength machinery of Lapack. Are there any ...
6
votes
1answer
95 views

How to know which LAPACK's function is used by Scipy's eig function?

As far as I understood, scipy.linalg.eig use wrappers from scipy.lapack to compute the eigenvalues and eigenvectors of a matrix. ...
6
votes
1answer
162 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\...
6
votes
1answer
677 views

Wrong Result QR decomposition with Pivoting in LAPACK

I am trying to use LAPACK geqp3 function for QR decomposition with pivoting but result is wrong. I tried almost two days but can't figure out the problem. I compared the result with Matlab and Python ...
6
votes
2answers
3k views

Calculating the log-determinant of a large sparse matrix

I need to calculate $\log(\det (\mathbf M_i))$ where the $\mathbf M_i$'s are large sparse matrices, which are real, symmetric and positive semi-definite. I hope to have between $10$ and $100$ of ...
6
votes
1answer
1k views

generalized eigenvalue problem

I need to solve a real generalized eigenvalue problem $Ax= \lambda Bx(*)$ A and B are calculated from equations below: $$A=\sum_{i,j=1}^{N}W_{ij}(K_{i}-K_{j})\beta\beta^{T}(K_{i}-K_{j})^{T}$$ $$B=\...
6
votes
1answer
177 views

Fast multiplication of highly structured matrix

I want to compute a fast matrix-vector product using a matrix $T$ which has a peculiar quasi-Hankel structure. For example, \begin{equation} T_2= \left( \begin{array}{c|ccc|cccccc} a & b & c &...
6
votes
1answer
402 views

Fast algorithm for computing matrix square root using randomized linear algebra?

Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?
6
votes
3answers
3k views

Fast algorithm for Polar Decomposition

As it known, according to the Polar Decomposition, square matrix can be expressed in the next form $$M=QR$$ ($Q$ - orthogonal matrix $R$ - positive-semidefinite Hermitian matrix) I need to find this ...
6
votes
1answer
1k views

Generalized Singular Value Decomposition: only compute the r largest singular values

I want to compute the Generalized Singular Value Decomposition for sparse matrices with a size of up to 1000000 x 1000000 (not necessarily square). The method is going to be used in machine learning (...
6
votes
1answer
775 views

Effects of Lumping Mass Matrix

I've recently finished an introductory course on the finite element method from a more mathematical perspective (following Brenner and Scott) and we were introduced to the finite element mass matrix ...
6
votes
1answer
535 views

Is there a faster method to compute the geometric series of a matrix?

I want to calculate the geometric series of a matrix $A$: $$S=I+A+A^2+\dots+A^n$$ and then apply to a vector $v$, $Sv$. I've done it in Matlab with a loop and I think it's quite efficient applying ...
6
votes
0answers
147 views

An invertible matrix that minimizes the norm of the product with a given matrix

Given a fat matrix $B \in \mathbb{C}^{n \times m}$ (where $m > n$) with full row rank, I would like to find (numerically) a full-rank matrix $A$ that minimizes the Frobenius norm of the product $A ...
6
votes
0answers
276 views

Compute sparsity pattern of $A^2$

Suppose we have a sparse matrix $A$. Is there any way to compute just the sparsity pattern of $A^2 = A \cdot A$ (I do not actually need to know what exactly the nonzero value are) faster than to ...
6
votes
0answers
417 views

What is the source of the error in the Sherman-Morrison formula application?

The Sherman-Morrison formula $$ (A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} $$ results in small errors in relation to the standard matrix inverse operation after each application, ...
6
votes
0answers
113 views

How does an unpivoted QR fail to reveal rank?

An unpivoted QR factorization produces a triangular factor $R$. A rank-revealing QR factorization is typically done with column pivoting. My question is, how does an unpivoted QR factorization fail to ...
5
votes
2answers
389 views

Recommendations for symmetric preconditioner

Given symmetric, positive-definite matrix $A$ and its preconditioner $M^{-1}$. What's kind of preconditioner $M^{-1}$ which preserve the symmetry of $M^{-1}A$?
5
votes
3answers
1k views

Efficiently computing the product of a multi-dimensional matrix (or tensor) and vectors

Update: Thank you very much for all of you who answered below. I'm studying each answer now. In the long term, I'm more interested in solutions that work for sparse tensors (sorry I should have ...
5
votes
3answers
2k views

What is the best solver for solving a large sparse indefinite system

What's the best solver that can solve a large sparse but indefinite matrix?
5
votes
2answers
151 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+...
5
votes
1answer
1k views

Why do libraries need hand-vectorized code instead of compiler auto vectorization

C++ eigen library does vectorization for different architecture, like SSE, NEON etc. In their documentation they mentioned that, Eigen vectorization is not compiler dependent. But most modern ...
5
votes
2answers
223 views

Inverting a pressure matrix for fluid simulation

I am implementing a fluid simulator as my numerical methods course project and I have to compute pressure at each simulation step. Basically, that means solving an equation $Ap = b$, where $A$ is a ...
5
votes
2answers
777 views

Big matrix multiplication on single machine

For example I have 2 matrices that can't fit in RAM. I need algorithm or library which can handle this.Preferably Matlab or Python. I think it can be some block matrix multiplication? Also I think ...
5
votes
2answers
222 views

Are there any specialized methods available for solving structurally symmetric sparse linear systems?

When solving $Ax=b$, prior knowledge about $A$'s structure can help in designing an efficient solver which exploits this information (e.g conjugate gradient method is to be used when $A$ is ...
5
votes
4answers
1k views

Efficient solver for a symmetric tridiagonal system where the upper/lower diagonals are offset

I'm looking for an efficient way to solve a symmetric tridiagonal system $Mx = d$, where the upper and lower diagonals of $M$ are offset from the main diagonal by $k$ rows/columns: $$ \begin{bmatrix} ...