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
4
votes
3answers
406 views

Evaluating large determinants with multivariate polynomial entries

I have some large (n~100) square matrices with entries two variable polynomials of bounded degree (roughly <20, but many entries are smaller) and integer coefficients, and I'd like to be able to ...
4
votes
2answers
2k views

Optimization with matrix determinant as constraint

I'm solving a constrained optimization for matrix $\mathbf{A}$ with dimension 6x6, where one of the constraints is $\mathrm{det}(\mathbf{A})>0$. I use the NLopt package to solve my problem and ...
4
votes
1answer
715 views

Libraries for distributed-memory Cholesky factorization?

What libraries can compute dense Cholesky factorizations in distributed-memory environments (preferably using MPI). I'm using C/C++, and have access to a cluster of between 1 and 40 nodes, where each ...
4
votes
2answers
5k views

Is there an MPI All Gather operation for matrices?

I have a distributed matrix, in block column format. I know that I can reshape the matrix into one long vector and use an all_gatherv operation. I just wanted to avoid the trouble of having to ...
4
votes
1answer
219 views

Accurate way of getting the square root inverse of a positive definite symmetric matrix

What is the most accurate algorithm to get the square root inverse of a positive definite symmetric matrix? I am not looking as much for efficiency, though using quadruple precision computation is out ...
4
votes
2answers
265 views

How “sparse” should a sparse matrix be to see benefits?

I have a matrix, whose size scales as $2^N$ (assume even $N$). In each row of the matrix, only about $2^{N/2}$ of the entries are filled ($N$ can be somewhere between 10 and 40, depending on what's ...
4
votes
1answer
129 views

Using GSL for basic operations

I am learning C/C++ for Scientific Computing and I have a question regarding the usage of scientific libraries for basic operations. Suppose I have to write a small program in C for a bioinformatics ...
4
votes
1answer
2k 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$ ...
4
votes
1answer
248 views

What is the most efficient way to obtain the max eigenvalue of a specific symmetric matrix via Eigen C++

Suppose I have a symmetric matrix $A_{1000\times 1000}$, which can be represented by: $A = J G J^T$ where $J$ in 1000x3 is full column rank dense matrix; $G$ in 3x3 is a nonsingular dense matrix. ...
4
votes
2answers
2k views

Reordering sparse matrices in computational science

On page 3 of this document, there are some matrix forms for sparse matrices. I wonder if there are other forms used in computational problems encountered in physics, chemistry, etc., so that ...
4
votes
1answer
257 views

Fast algorithm for computing cofactor matrix

I wonder if there is a fast algorithm, say ($\mathcal O(n^3)$) for computing the cofactor matrix (or conjugate matrix) of an $N\times N$ square matrix. And yes, one could first compute its determinant ...
4
votes
2answers
184 views

MATLAB Matrix Multiply Efficiency

I am using MATLAB to prototype a few matrix multiply techniques and compare efficiency. Eventually, I will move the prototype codes to C. It is for a homework assignment where we need to write an ...
4
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 ...
4
votes
1answer
114 views

Does $\log(\det(A))$ equals sum of log of diagonal elements of D in LDLT decomposition?

For a large matrix $A$, I need to evaluate the $\log(\det(A))$. I already have it's LDLT decomposition. Is it possible to evaluate the $\log\det$ with the elements of the diagonal $D$ of the LDLT ...
4
votes
1answer
4k views

Power Iteration on general matrices (with higher multiplicity of dominant eigenvalue)

To compute the eigenvector corresponding to a dominant eigenvalue of a matrix $A\in\mathbb{R}^{n\times n}$, one could apply the Power Iteration: $$v_1=\frac{Av_1}{\|Av_1\|}.$$ 1) in case $A$ is ...
4
votes
1answer
130 views

Constructing the origin position by transforming distance information

Suppose a set of $n$ points, $n\in M$, is given in some $d-$dimensional space, $X\in\mathbb{R}^{n\times d}$. Among these $n$ points, some $k\in K$ are selected, so $k<n$, and the distances from ...
4
votes
3answers
458 views

Inverse of ill-conditioned symmetric matrix

I've got a matrix K, with dimensions $(n, n)$ where each element is computed using the following equation: $$K_{i, j} = \exp(-\alpha t_i^2 -\gamma(t_i - t_j)^2 - \...
4
votes
1answer
50 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
4
votes
1answer
1k views

What is wrong with this matrix multiplication?

I am attempting to write a matrix multiplication routine because I need to do some analysis in CUDA and I want to validate it with CPU code. I am trying to use <...
4
votes
2answers
1k views

Computational complexity and implementation of UDU Modified Cholesky Rank 1 Update

I am attempting to increase the performance of a legacy Kalman Filter implementation. The state covariance is factored in terms of UDU, i.e. $\mathbf{P} = \mathbf{U}\mathbf{D}\mathbf{U}^T$. Many ...
4
votes
2answers
2k views

Algorithm for Sparse-Matrix Inverse

I have a $50000\times 50000$ matrix $A$ sparse matrix containing only 5 non-zero elements in each row. Now the problem is that the diagonal elements and the constants (in $B$ matrix such that $AX=B$) ...
4
votes
1answer
1k views

How to do transpose for trtrs (or tptrs) in blas?

How to do transpose for trtrs (or tptrs) in blas? I want to solve: XA = B But it seems that trtrs only lets me solve: ...
4
votes
1answer
339 views

$\mathbf{UDU}^\top$ decomposition routines in LAPACK/Eigen?

I would like to compute the decomposition of a real symmetric positive definite matrix $\mathbf{A} = \mathbf{UDU}^\top$. LINPACK seems to have it as DSIFA, but I ...
4
votes
1answer
294 views

Sparse LU for block-sparse matrices

I frequently need to solve linear systems with sparse matrices of moderate dimension (say a few thousand). These matrices are composed entirely of small dense blocks (typically 5-10 in dimension), and ...
4
votes
2answers
79 views

Any reference which summarizes decompositions?

Is there any reference (preferably available online as PDF, Free would be best) which summarizes the various matrix decomposition with their conditions for use, usage, algorithm, complexity and ...
4
votes
2answers
870 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 ...
4
votes
1answer
748 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 ...
4
votes
1answer
133 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, ...
4
votes
1answer
442 views

Obtaining column vectors of pseudo-inverse of a matrix

I need to compute the pseudo-inverse of a very large rectangular dense matrix without any special structure or properties. I run out of memory/computing power and have no access to a large parallel ...
4
votes
1answer
119 views

Is there an efficient $O(n^2)$ way to get the eigen decomposition given a LDL factorization?

Let's say I have a LDL factorization of a matrix A. Is there an efficient $O(n^2)$ way to get the eigen decomposition of A given it's LDL factorization? Is there a more efficient way, in case L and ...
4
votes
1answer
117 views

Comparing Two Matrix Notation

I have two matrix A and B, I want to find pattern B in matrix A. So I get 2 pattern similar like pattern B. What the name of this operation? and How I write this in mathematics notation? Thank you in ...
4
votes
1answer
164 views

Updating an approximate solution to a linear system in response to a small change

This question was original posted on SO but it was suggested that I post it here. I'm working on a program in which I have a banded matrix M and a vector b, and I want to maintain an approximate ...
4
votes
2answers
875 views

How can you calculate percent error in tensor approximations?

I have a matrix A which is an approximation to the known matrix B. Both matrices are square, 3x3 matrices and, in this case, are ...
4
votes
1answer
54 views

Configuration shift for determination of a true dimensionality

What would then be the way to determine a true dimensionality of a configuration of points $X\in\mathbb{R}^{n\times k}$ based on its Gram matrix $G=XX^T$? The "true" dimensionality refers to the ...
4
votes
3answers
222 views

Efficiently computing a few localized eigenvectors

Let $H = \triangle + V(x) : \mathbb{R}^2 \rightarrow \mathbb{R}^2$. I am interested in domain decomposition for an eigenproblem involving $H$. The lowest 1000 eigenfunctions of $H$, $ \psi_i $, can ...
4
votes
1answer
400 views

What is the fastest method to invert millions of matrices?

My project involves large simulation and estimation. For each simulation I need to solve 600,000 systems of nonlinear equations. Currently I am using Newton's method to find the solutions. That ...
4
votes
1answer
160 views

Factorization for reweighted least squares

I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares Essentially this requires solving a number of least-...
4
votes
0answers
91 views

Fastest matrix library for Android (with GPU is possible)

I was working on an Android app that requires some linear algebra with matrices. The matrices will be somewhat medium-sized as they are not too small or too big. I was originally using jBlas because ...
4
votes
0answers
78 views

Block matrix and DSYRK

I want to compute the matrix $$ A = \sum_{i=1}^N v_i v_i^T $$ where each $v_i$ is a given vector of length $2500$, so that $A$ is $2500 \times 2500$, and my $N$ is about 2 million. Rather than call ...
4
votes
0answers
116 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 ...
4
votes
0answers
199 views

Alternative to (costly) matrix multiplication

Consider the integral $$2\pi T = -\frac{1}{2} \int_0^{2\pi} A\frac{\partial B}{\partial \xi} \ d\xi$$ where $$A= \sum_{-N}^N i \ sign(n) \ B_n e^{-in\xi}; \quad \quad B= \sum_{-N}^N \ B_n e^{-in\xi}...
4
votes
0answers
143 views

How big a matrix can we row reduce in reasonable time?

I have very large matrices that I would like to row reduce (I need to keep track of the steps and find a basis of the kernel/image, not just find the rank). The good news is that I work mod 2 and the ...
4
votes
0answers
100 views

Tracking for two meshes

I'm dealing with physical simulation (position based dynamic). Now I'm trying to realize tracking for two meshes. In order to explain what does it mean, let's assume that we have two similar meshes: ...
4
votes
0answers
683 views

Generating pseudo-random orthonormal bases for random projection

I am performing series of random projections i.e. projecting the input matrix onto randomly generated orthonormal bases (of much lower dimensionality). The projection is just a matrix multiplication ...
4
votes
0answers
659 views

Perron-Frobenius theorem on general real symmetric matrices

From the Perron-Frobenius theorem, it might be concluded that the spectral radius is the largest eigenvalue for positive matrices, ie, matrices with strictly positive entries. In other words, the ...
4
votes
0answers
134 views

Probabilistic algorithms for matrix approximation

Considering regular matrix approximation inequality || $A - QQ^TA $|| < e where we try to approximate matrix $A$ by a lower rank orthonormal matrix $Q$. I've read an article on probabilistic ...
3
votes
3answers
3k views

Fast vector - “diagonal” matrix multiplication

Let $\mathbf{1}\in\mathbb{R}^d$ be a vector with all elements equal to $1$. Define: $$\mathbf{D} = \mathrm{diag}(\mathbf{1}^\top,\mathbf{1}^\top,\ldots,\mathbf{1}^\top) = \begin{bmatrix} 1 \cdots 1 &...
3
votes
1answer
2k 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
4answers
8k views

cartesian products in numPy

Have two arrays, in my case $X = \{1,2,\dots, n\}$ or X = np.arange(n). How do I get $Y = X \times X = \{ [i,j]: 1 \leq i,j \leq n \}$ as a 2D array in numPy? ...
3
votes
2answers
250 views

Positive semi-definiteness of a (symmetric) matrix

Suppose a matrix $A\in\mathbb{R}^{n\times n}$ is given. Faced with a proof for $$x^TAx>0,$$ for a non-zero vector $x\in\mathbb{R}^{n}$, I was thinking to use the information of the spectrum of $A$ (...

1 2 3
4
5
11