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 [matrix]

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

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

Speed up matrix calculation in R

I'm simulating in R a Geometric Brownian Motion, for different correlated companies (nComp), and number of days (nDays). Wt are the the correlated Brownian paths. I'm running the following code, for ...
2
votes
1answer
344 views

Fast C++ implementation of sparse binary matrices

I am looking for the subject. The size of matrices will be around 1000x2000 elements with linear amount of ones (say, 6000 ones in the whole matrix). The operations I will use the most: iterating ...
4
votes
1answer
117 views

In constructing matrices to model physical phenomena, are real matrices superior to complex matrices, in terms of computational cost?

Just studying some toy examples of $2\times 2$ and $3 \times 3$ matrices, complex number multiplication already gets a bit messy. From a numerical analysis point of view, if one were to try and build ...
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. ...
1
vote
2answers
303 views

Defining a pixel neighborhood in an array in MATLAB

I am working with matrix operations in MATLAB, and I would have the following problem. I have matrix containing zero elements: a=zeros(100,100) and another ...
2
votes
1answer
861 views

Applying the result of Cuthill-McKee in SciPy

I have applied SciPy's implementation of the Cuthill-McKee algorithm to a $48 \times 48$ sparse non-symmetric matrix in Compressed Sparse Row (CSR) format and the output is an array of length $48$ ...
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
2answers
102 views

Data cloning into 3D matrix

I am working with MATLAB, and I would have the following problem. I have the following matrix of random numbers rand(200,200) and I need to create a 3D matrix ...
1
vote
0answers
130 views

Mutual information of Multivariate Gaussian Distribution [closed]

Consider N random variables $\mathbf{x}=[x_1,x_2,...,x_N]^T$ with joint density $p(\mathbf{x})$, and let $\mathbf{R}\in \mathbb{R}^{N\times N}$ denote the covariance matrix. How to derive the mutual ...
3
votes
1answer
479 views

How to improve this double-shift QR algorithm for non-symmetric matrices?

I've implemented a version of the double-shift QR algorithm featured in this report from ETH Zurich (Begins on page 77). The algorithm takes advantage of the Implicit Q theorem by applying an ...
0
votes
1answer
81 views

Multiplication of random sparse matrices

I am given 2 unstructured (i.e. do not posses any special sparsity pattern like banded/triangular/etc.) sparse matrices $A$ and $B$ of dimension ($n$ x $n$) and density $d$ each (thus each matrix ...
0
votes
1answer
174 views

Linear solve using CHLOMOD in C

I am using the open-source CHLOMOD (as here http://faculty.cse.tamu.edu/davis/suitesparse.html) in order to solve a linear system Ax=b (performing A/b=x) in my domain decomposition code but I am ...
0
votes
1answer
161 views

Open Source Linear Algebra Library

I am making a code in C that requires the equivalent of Matlab's '\' command for a linear system of the form AX=B where A is an NxN matrix and X, B are Nx1 vectors- i.e a code that performs X=A\B that ...
4
votes
1answer
544 views

Vectorize a part of a huge matrix in C++

I have a large matrix, side-length is about $n\geq 1000$. I need to do element-wise multiplication of this matrix with another matrix many, many times. I make this process by: Vectorizing (through ...
7
votes
2answers
112 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 ...
5
votes
1answer
905 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 ...
1
vote
1answer
86 views

Mapping from n x n complex symmetric tridiagonal to 2n x 2n real symmetric tridiagonal

In my program I have a complex symmetric tridiagonal matrix. In order to perform some algorithmic optimizations I am searching for a (ideally linear) mapping from $n\times n$ complex symmetric ...
7
votes
1answer
510 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 ...
4
votes
0answers
354 views

Sparse matrix format and sparse-matrix sparse-matrix multiplication

Good morning, I'm having some performance problems with my code dealing with the multiplication of big sparse matrices (stiffness and aerodynamic influence coefficient matrices). Mainly I have to ...
0
votes
1answer
65 views

Show the symmetric Gauss-Seidel converges for any $x_0$

Let $A\in\mathbb{R}^{n\times n}$ is symmetric positive definite and consider solving linear system $Ax = b$. Show that the symmetric Gauss-Seidel iteration converges for any $x_0$. Solution - Since $...
3
votes
1answer
174 views

Efficient algorithm for a matrix product

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
3
votes
1answer
200 views

Determine a sufficient condition for a Hessenberg matrix to be nonsingular

Consider $A\in\mathbb{R}^{n\times n}$ whose nonzero elements are restricted to the main diagonal the strict upper triangular part, and the first subdiagonal. For $n = 8$ the locations that must be ...
2
votes
1answer
150 views

Schur complement of a matrix $A$

Let $A\in\mathbb{R}^{n\times n}$ and its inverse be partitioned $$A = \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22}\\ \end{pmatrix},\:\: A^{-1} = \begin{pmatrix} \tilde{A_{11}} & \...
0
votes
1answer
151 views

Parallel linear algebra without OpenMP

I have searched through the archives without success. Apparently, the question is simple: What linear algebra library can I use that is parallel (shared memory) but without OpenMP? As far as I've ...
5
votes
0answers
266 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 ...
0
votes
0answers
32 views

Can I exploit symmetry in a two-sided matrix product A*S*transp(A) to gain execution speed?

Let $A$ and $S$ be $n \times n$ matrices. Only $S$ is symmetric. What is the fastest algorithm to compute $S := A S A^T$?
2
votes
0answers
257 views

Fixing a near singular covariance matrix

Given a near singular covariance matrix, the standard method of 'fixing' it seems to be to add a small damping coefficient $c>0$ to the diagonal, which serves to bump all the eigenvalues up by this ...
1
vote
1answer
52 views

Use double index in matrix multiplication

I want to run a simulation which involves rates between different states. Each state is label by a pair of indices $(m,n)$, so that a certain rate $R_{(m,n)\rightarrow(m',n')}$ requires four indices ...
4
votes
2answers
973 views

Stabilizing a 3x3 real symmetric matrix eigenvalue calculation

I have many 3x3 real symmetric matrices for which I need to determine the eigenvalues. Wikipedia gives a nice non-iterative algorithm for this case, which I have translated into C++: ...
4
votes
1answer
227 views

Mobile robot path following using model predictive control (MPC)

I'am trying to implement a path following algorithm based on MPC (Model Predictive Control), found in this paper : Path Following Mobile Robot in the Presence of Velocity Constraints Principle: ...
1
vote
1answer
465 views

Armadillo Multi-threaded Linear Solve Yielding Different Answers

I'm working on some problems that ultimately boil down into a simple assembly of an overdetermined system of equations, $Ax=b$, where $A$ is $m \times n$ for $m \gg n$. I'm leveraging Armadillo's C++ ...
2
votes
2answers
535 views

Sparse Matrix Matrix multiplication terminology (SpGEMM or SpMM?)

I have seen sparse matrix-matrix multiplication commonly referred to as SpGEMM, which means general/generalised sparse matrix-matrix multiplication. I've seen it once or twice (forgot where) as SpMM. ...
0
votes
1answer
67 views

Construct tridiagonal matrix from eigenvalues

I have a sort of reverse problem, and I'm not sure if there is a simple solution. I have a tridiagonal Hermitian matrix: $$ A = \begin{bmatrix} 0 & a_1 & 0 & 0 & 0 \\ a_1 & 0 &...
1
vote
1answer
68 views

Creating a matrix that saves storage

Suppose $A\in\mathbb{R}^{n\times n}$ is a banded matrix, i.e., a matrix with all of its nonzero elements on the main diagonal, i.e., $\alpha_{i,i}\neq 0$, the first superdiagonal, i.e., $\alpha_{i,i+1}...
2
votes
1answer
91 views

Condition Number of Rectangular Matrices

The 2-norm condition number can be easily extended to rectangular matrices. I'm wondering if the inequality for the product of matrices still holds in that case, i.e., $\operatorname{cond}(AB) \leq \...
4
votes
1answer
157 views

Algorithm to decompose a sparse unitary matrix into a Kronecker product of smaller unitary matricies

Given some sparse unitary square matrix $A$ ($dim=2^n$ if it matters), is there an algorithm to decompose $A$ into a Kronecker/tensor product of smaller unitary matrices? In other words: decompose ...
1
vote
1answer
570 views

Matrix transpose multiplication

In CVX, I encounter a problem. I want to multiply a Matrix of 2x4 with its transpose. I know the result must be positive definite. However, it couldn't let me do the multiplication directly. Says: ...
2
votes
2answers
1k views

Methods for fast approximation of convolution

What are the state of the art methods for fast 2D convolution approximation? I'm familiar with SVD based multiplication and cross approximation approaches, but would be thankful to get additional ...
0
votes
0answers
344 views

Preconditioned Conjugate Gradient linear system solver in MATLAB

I have been trying to use the MATLAB's pcg() function to minimize an energy functional. Converting minimization problems to the solution of a linear system is ...
10
votes
1answer
217 views

The fast, and The Backward-Stable (left) $3\times 3$ matrix inverse

I need to compute a lot of $3\times3$ matrix inverses (for Newton iteration polar decomposition), with very small number of degenerate cases ($<0.1\%$). Explicit inverse (via matrix minors divided ...
4
votes
1answer
123 views

Efficient way to generate a list of possible matrices (all integer components) with a determinant $V$

I have an interesting problem from my research that I have been struggling to solve. One part of the problem involves generating all possible matrices, where each set contains three integer vectors, ...
0
votes
1answer
151 views

Fast computation of square root inverse of matrix, matrix being determined from Ax=b form

I have an equation of the form $J^Te=f$, where $e$ and $f$ are known vectors and $J$ is an unknown matrix. How can I efficiently compute $J^T(JJ^T)^{-1/2}e$ ? My motivation to address this problem ...
0
votes
1answer
149 views

Is there any rapid way to calculate the determinant of NXN covariance matrix?

I searched the web and found some C code for calculating the determinant of a $n\times n$ matrix. This code however seems timing complexity, and run pretty slow especially when handling a larger ...
1
vote
0answers
36 views

Optimal distribution of zeros and ones over matrix

I have the following problem: Given a matrix with n rows and m columns. Some elements of the matrix are unavailable. For each column, you have a set containing a number of zeros and ones which must ...
4
votes
1answer
358 views

How to read a Harwell-Boeing Matrix file format into a compressed sparse row format in a C program?

I have to write a program where I have to perform matrix-vector multiplication and the matrix is sparse matrix. Most sparse matrices available online are in Harwell-Boeing format and they have to be ...
3
votes
1answer
516 views

strassen algorithm vs. standard multiplication for matrices

I am trying to figure out at exactly what dimension it is better to use Strassen algorithm rather than the standard multiplication. I know that there is 18 addition and subtraction in Strassen ...
2
votes
0answers
81 views

Solve for $D$ in $R^{T}DSDR = Id$

Given that $R$ is a rectangular matrix, $D$ is a diagonal, square matrix and $S$ being a square matrix along with the fact that both $D$ and $S$ are invertible. $S$ in this specific case can be ...