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
1
vote
1answer
164 views

GPU libraries for integer matmul | overflow tolerated

Are there any high performance integer BLAS libraries that implement matrix multiplication i.e. i32gemm and i64gemm ? I need to use them for a cryptographic application and can tolerate overflows, i.e....
1
vote
1answer
388 views

LAPACK sorting eigenvalues differently each time

I'm using LAPACK zgeev routine to get eigenvalues and eigenvectors of a symmetric matrix in C++. Problem is zgeev is being called in a loop but it sorts eigenvalues (and eigenvectors) differently ...
3
votes
1answer
2k views

Computing the Cholesky decomposition based of the QR decomposition

Let A be a n×n positive-definite Hermitian matrix. I already have the QR decomposition of A. Is there an efficient way to utilize this knowledge to speed up the Cholesky decomposition of A?
1
vote
1answer
95 views

Efficiency of Array Slicing

I have large arrays of data organized so that it can be processed efficiently using array processing libraries. However, there are times when I only need to process slices of the arrays where a slice ...
1
vote
0answers
405 views

Vectorizing Matrix Multiplication

I would like to do the following operation: I have a "4D" matrix A and a "3D" matrix B. Both A and B are actually 2D matrices, where for A, each element is a 2D matrix, and for B, each element is a 1D ...
3
votes
2answers
128 views

Sharing a matrix with the math community

What would currently be the best way to share a matrix with the math community? (I'm aware of Matrix Market but it seems the last update was in 2007...)
0
votes
1answer
75 views

How to do matrix operations with this way of storing sparse matrices

I read the way of storing the five or seven point laplace matrix for some poisson problem but I don't understand how can i multiply, add and subtract this stored sparse matrix by a vector or another ...
13
votes
4answers
286 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, ...
0
votes
1answer
90 views

Sparse matrix inverse with reduced bandwidth

I have a sparse symmetric matrix of dimension 1393x1393 (8308 no zero elements), with bandwidth 1380. By Cuthill–McKee algorithm, I could achieve a new matrix with ...
1
vote
0answers
154 views

Best algorithm for inversion of matrix spanning many orders of magnitude [duplicate]

I have a very similar problem to the one described in Calculate inverse of dense matrix with entries of very different magnitude. The reason why I am opening a new question is because as far as I ...
1
vote
1answer
166 views

Implicit method for two coupled PDEs

I have two equations (coupled), with the variables $T_1$ and $T_2$ and the constant $T_0$, which are (when written unitless, i.e. without prefactors): $$\partial_t T_1 = 1-T_1^3+T_1+\nabla\left(\frac{...
2
votes
1answer
564 views

Regularization vs constrained optimization of an ill posed tomography problem

I am trying to solve an ill-posed linear system of equations. The particular system has 160 equations and 400 variables. Moreover, the condition number of the left hand side matrix is of order $10^{16}...
0
votes
1answer
72 views

Invert a matrix only on a subset of variables / Compute the “equivalent circuit”

Suppose I have a complicatedly shaped conductor with inhomogeneous conductivity. The conductor is modeled using the Finite Element Method. The conductor has electrical contacts on both ends. Those ...
4
votes
0answers
108 views

How to stochastically estimate the trace of a matrix?

Specifically, the diagonal elements (can possibly both positive and negative) of the matrix can be computed efficiently but the total number is large ($\mathcal O(10^{18})$). My first thought about ...
3
votes
1answer
514 views

Why is the speed of the parts of the LU-decomposition so different?

I know that an easy way to solve the matrix problem $$A\cdot x=b$$ is the LU decomposition $$\begin{split} L,\,U&=\text{lu}(A)\\ y&=\text{solve}(L,\,b)\\ x&=\text{solve}(U,\,y) \end{split}$...
0
votes
2answers
99 views

Benefits of matrix multiply over inversion

I have two variations of an iterative algorithm. All the steps of both algorithms are equivalent except one. In this step: Algorithm 1 needs to compute the matrix $ABA^T$ for matrices $A \in \mathbb{...
1
vote
0answers
47 views

Any method to efficiently compute SVD of a perturbation of matrix $\bf A$ if the SVD of $\bf A$ is already known? [duplicate]

Suppose we know the SVD of matrix $\bf A$, and $\bf B$ is a slight perturbation of $A$ (e.g. $\|{\bf B}-{\bf A}\|_{\text F}$ is relatively small), then is there any method that can efficiently compute ...
1
vote
1answer
188 views

Fast counting of all submatrices of a binary matrix with a full column rank

I have a binary full-rank matrix of size, say, $25 \times 50$. I need to count how many subsets of its columns form matrices with a full column rank, i.e. all the columns in the subset are linearly ...
2
votes
1answer
451 views

Distributed (MPI) matrix matrix multiplication

I perform matrix matrix multiplications (between rank-3 and rank-2 arrays) in fortran using following subroutine, ...
3
votes
1answer
3k 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 ...
2
votes
2answers
85 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
91 views

Problem in analyzing the program of Gauss Jordan Inverse problem

I had to code a program which calculates Inverse of a matrix by Gauss-Jordan Inverse method , I was trying to analyse the program and then code it myself. the link http://hullooo.blogspot.in/2011/...
16
votes
2answers
1k views

Practical example of why it is not good to invert a matrix

I am aware about that inverting a matrix to solve a linear system is not a good idea, since it is not as accurate and as efficient as directly solving the system or using LU, Cholesky or QR ...
2
votes
1answer
319 views

Preconditioner for dense matrix “with diagonal predominance”

For a CFD panel-based potential method, I'm trying to reduce the time to solve the linear system. The matrix has the larger values on the diagonal, since the influence of a panel on itself is maximum, ...
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 ...
4
votes
0answers
342 views

Optimisation of matrix exponential

I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 ...
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+...
1
vote
2answers
283 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 ...
1
vote
2answers
685 views

LU decomposition of large dense matrices

I wanted to generate LU decomposition of large size dense matrices ($N>10^7$), the LU decomposition I'm currently using is based on Adaptive Cross Approximation and is taking very long time to ...
2
votes
0answers
179 views

Fast solution of a heptadiagonal linear system

I have a linear system of the form $\mathbf{A}\mathbf{x} = \mathbf{f}$. If the length of the vector $\mathbf{x}$ is $N$, meaning that there are $N$ unknowns, then the matrix $\mathbf{A}$ has seven ...
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 ...
0
votes
1answer
82 views

MATLAB: Matrix whose elements depend on its indicies

I am trying to put the function $$ f(\mu,\nu) = i^{\nu-\mu} \sum_{0}^{19} H_{\mu-\nu}(7j) + \delta_{\mu,\nu}\ ,$$ $\mu, \nu =-3,-2,...2,3$ into a 7x7 matrix, where $H$ is the Hankel function of the ...
1
vote
0answers
58 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 ...
0
votes
2answers
69 views

Accuracy between ill-conditioned matrix-free vs. matrix-based operators

As far as I know, precision errors become larger as the condition number of a matrix increases. Consider a matrix-based operator: $$A = \nabla \bullet k \nabla $$ And a matrix-free operator: $$\...
0
votes
3answers
693 views

Matrix of linear transformation in MATLAB

How can I determine a matrix $R$ in matlab such that, given a known matrix of coefficients $A$ gives me back its row reduced echelon form? Obviously I need an algorithm/function that works also with ...
1
vote
2answers
172 views

numerically stable routines to compute $M = B A^{-1} B$

Rather than gesv -> solve $AX = B$ gemm -> compute $M = BX$, somehow I feel there are better ways to compute $M$ with lapack/mkl?
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 ...
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?
1
vote
1answer
7k views

Implementation of the Jacobi iteration to find the solution to $Ax = b$

I implemented the Jacobi iteration using Matlab based on this paper, and the code is as follows: ...
4
votes
3answers
3k views

Beating typical BLAS libraries matrix multiplication performance

A dull matrix multiplication algorithm where we use the formula $$C_{ij}=\sum_{k}A_{ik}B_{kj}$$ By literally following this in 3 loops we'll get a very slow program, because we don't utilize ...
4
votes
2answers
743 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 ...
2
votes
2answers
1k 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 ...
13
votes
2answers
2k 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
410 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
120 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
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-...
2
votes
2answers
692 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
338 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
1k 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$ ...
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\...