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
5
votes
4answers
2k 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} ...
5
votes
1answer
897 views

restriction and interpolation in multigrid method

I need detailed explanation of the formula below A2=I1*A1*I2 I suppose this formula computes matrix A2 on a coarse grid and here A1 is original matrix on fine ...
5
votes
2answers
111 views

Choose a subset of $m$ columns that maximize $|A^T A|$?

I have a set of $n$-dimensional vectors, and would like to choose $m$ of them to become the columns of an $n\times m$ matrix. I would like to choose the subset that maximizes $|A^T A|$, where $A^T$ is ...
5
votes
3answers
1k views

Performance optimization or tuning possible for Scalapack Gemm?

I'm comparing the performance of distributed gemm, using Scalapack over OpenBLAS, with threaded gemm, using OpenBLAS. It seems quite hard for me to get scalapack to give better results than ...
5
votes
2answers
209 views

Imposing invertibility on a Matrix

I have a symmetric positive semidefinite covariance matrix $A$, which is approximately computed as the output of a quadratic regression. I then need to invert $A$, but often it is close to singular. I'...
5
votes
2answers
148 views

What is the algorithm for computing block reflectors in xDLARFB

The theory behind computing a single Householder reflector to zero out part of a column of a matrix is pretty well described in Matrix Computations by Golub and Van Loan. However, the blocked ...
5
votes
3answers
323 views

Methods for solving linear systems

This is such a basic topic but there are so many different methods proposed for solving a linear system of equations. I recently found a very good source but couldn't really make sense of all the ...
5
votes
1answer
146 views

Algorithm to factorize matrix whose many rows are already of upper triangular form?

I have a matrix whose many rows are already in the upper triangular form. $$\begin{bmatrix} x_{11} & x_{12} & x_{13} & x_{14} & x_{5} \\ 0 & x_{22} & x_{23} & x_{...
5
votes
2answers
573 views

Perturbation of Cholesky decomposition for matrix inversion

I am looking for a computationally cheap way to compute $x$ such that $$(L L^T + \mu^2 I)x = y$$ where $L \in \mathbb{R}^{n \times n}$ is a lower triangular definite positive matrix (with some very ...
5
votes
2answers
645 views

find a set of linearly independent columns in a $m\times n$ matrix

my question is between mathematics, physics and informatics. Suppose i have an Hamiltonian (hermitian matrix) that i can diagonalize. The matrix that allows this transformation is a unitary matrix ...
5
votes
1answer
112 views

Are there any algorithms “incrementally remove part of data (esp., old data)” from the existing SVD model of a data?

Sometimes it is meaningful to remove the influence of some old data from a SVD-based model, so as to reflect the most updated trends and provide more accurate results. I've seen there're incremental ...
5
votes
1answer
195 views

What Linear Equation Solver should be used for a problem with many dirichlet conditions?

I am solving a laplace equation on a finite-element mesh (tetrahedral, triagonal) and have many say 99% dirichlet conditions compared to the number of unknowns. Is there an efficient way to solve this ...
5
votes
2answers
615 views

Efficient computation of Markov chain transition probability matrix

Consider a continuous Markov chain $X=(X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...
5
votes
1answer
201 views

What is the difference between MATSEQMAIJ and MATSEQAIJ in PETSc?

What is the difference between MATSEQMAIJ and MATSEQAIJ in PETSc? Also, where can I find more information on each of the MatTypes? I went to the MatType documentation, but it didn't have anything but ...
5
votes
2answers
291 views

Is it possible to prove that the off-diagonal blocks of the Cauchy matrix have numerical rank $O(\log n)$?

Suppose we have a $n\times n$ Cauchy matrix of which the $ij$-th entry is given by: $$ A_{ij} = \frac{1}{a_i - b_j} $$ the assumption is that the distance between $\{a_i\}$ and $\{b_j\}$ is greater ...
5
votes
1answer
184 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. ...
5
votes
1answer
161 views

Fastest way to calculate the $2$-norm (or an upper bound for the $2$-norm) of the inverse of a matrix $A\in \mathbb{C}^{N\times N}$

I have a matrix $A\in \mathbb{C}^{N\times N}$ and I need to calculate $||A^{-1}||_{2}$ efficiently. Can it be done without having to evaluate the inverse explicitly? In general, I am looking for ...
5
votes
1answer
50 views

Transform from linear index of a packed triangular matrix to dense indices

Given indices $i,j$ s.t. $0\leq i \leq j <n$, the function $f(i,j)=i+j(j+1)/2$ maps 2d indices to linear indices in column major order. What is the fastest way to invert this function? My first ...
5
votes
1answer
187 views

Finding all binary vectors with given A-length

I am given a $n \times n$ matrix $A$ with real entries and define the inner product $$\langle x,y\rangle = x^T A y.$$ I am also given an integer $k$ and need to find all binary vectors $x$ such that $...
5
votes
1answer
761 views

What is a good way to take fractional powers of a matrix in MATLAB?

I am working on a problem that involves taking fractional powers of particular matrices. For the matrix A with 2 on the main diagonal and -1 on the sub and super diagonal (the finite difference ...
5
votes
1answer
1k views

Nullspace algorithm for a sparse matrix

I am dealing with large, sparse, rational matrices that I need to determine the nullspace of. Currently, I have one that is about 12000x12000 (but not square), where one in every 2000ish elements is ...
5
votes
2answers
285 views

Out-of-core matrix transpose of row compressed data

Summary: Are there good algorithms for out-of-core dense matrix transpose if each row of the matrix is separately compressed? Details: The matrix is about 1 TB uncompressed, and is roughly but not ...
5
votes
2answers
196 views

Computing any element of the null space of a singular matrix

Given a singular matrix $A$, what is the fastest method to find a single non-zero solution to $Ax=0$? Note that we are not looking for the whole kernel, we just want any non-zero vector in it. I ...
5
votes
1answer
164 views

How can I apply Euler's Method to predict a point in time rotating around multiple axis'

I am xposting this from my original stackoverflow question where I was presented with a coding challenge that I have been able to narrow down extensively and I think it lies with Euler's Method. Here'...
5
votes
1answer
193 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 ...
5
votes
1answer
136 views

Generate approximately semi-orthogonal tall matrix approximately satisfying constraints

I have a set of matrices $\{(A_i,D_i)\}$ for $i\in\{1,\ldots,n\}$, where: Each $D_j\in\mathbb{R}^{S\times S}$ is diagonal, and every entry on the main diagonal is non-negative. Each $A_j\in\mathbb{R}^...
5
votes
1answer
3k views

How to calculate ALL of the eigenvalues/eigenvectors of a large, sparse, asymmetric matrix?

I am trying to calculate all of the eigenvectors/eigenvalues of large (40000x40000), sparse, asymmetric matrix. I am using MATLAB and have 3 GB of working memory. The way I am calculating them is by ...
5
votes
1answer
263 views

What category is this problem?

My first question, please excuse me if its too basic. I have a matrix of evenly spaced geographical points; say 10 x 10, which I will call seed points. Each seed ...
5
votes
1answer
650 views

Sparse matrix ordering in Python

I would like to implement custom, domain-specific algorithms for sparse matrix orderings. I am looking for Python packages for ordering sparse matrices. It would be nice to have: The underlying ...
5
votes
1answer
798 views

Eigenvalue Decomposition of Hermitian Matrix in Scala

I'm working on helping my friend create code to perform the Overlap Dirac Operator and have come across one part that I'm not sure what to do. I need to compute the Eigenvalues and corresponding ...
5
votes
1answer
133 views

Configuration shift to change the rank of a Gram matrix

Suppose a matrix $D\in\mathbb{R}^{n\times n}$ of Euclidean distances between $n$ points is given. To obtain a Gram matrix (matrix of inner-products of points that give rise to distances in $D$), one ...
5
votes
0answers
73 views

Efficient way to find eigenvalues of complex symmetric matrix with real off-diagonal elements

My goal is to find all eigenvalues (and eigenvectors) in a given range of magnitudes of a complex symmetric matrix with real off-diagonal elements (only diagonal elements are complex). Currently I'm ...
5
votes
0answers
184 views

Polynomial rooting - fast root finding

I need to solve a rooting problem of a polynomial (the order of which is 2(N-1), where N=48). So far I'm using Python Numpy algorithm (that relies on computing the eigenvalues of the companion matrix)...
5
votes
0answers
557 views

Sparse matrix format and sparse-matrix sparse-matrix multiplication

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 multiply such ...
4
votes
4answers
1k views

Library that performs sparse matrix-vector and matrix-transpose-vector multiplication

My main interest is sparse matrix-vector and matrix-transpose-vector multiplication of the form y=y+AA'x. Is there any library that performs ...
4
votes
1answer
611 views

Numerically stable approach for calculating x in Ax=b

I have an equation $Ax=b$ for which I need to solve for numerous $x$ matrices given $b$. Both $x$ and $b$ are nx1 matrices. Unfortunately, $A$ is a 32x32 matrix and inversion gives highly unstable ...
4
votes
2answers
153 views

Simplifying some operations on Gram matrices

Suppose two Gram matrices are given $A, B\in\mathbb{R}^{n\times n}$, such that $$A=XX^T,~~~~~~~~~~~~~B=YY^T,$$ for some $X, Y\in\mathbb{R}^{n\times k}$, $k\ll n$. Also, suppose a Gram matrix based on ...
4
votes
2answers
2k views

Extracting a 2D matrix from a multidimensional array in C

In my c language program, I have to store multiple dense $m\times m$ matrices corresponding to gridpoints $x_i$ with $i=1,...,n$. I decided to create a three dimensional array $A\in R^{n\times m\...
4
votes
1answer
171 views

Do I really need to invert this matrix

I need to calculate a matrix $A$ (at least some elements of it, see below) as defined by the following equation $$ A=B(\mathbb{1}-B)^{-1} $$ where B is a square matrix of dimension $N$ and $\mathbb{...
4
votes
3answers
4k 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
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 ...
4
votes
1answer
3k views

Why is my MATLAB code for back-substitution slower than the backslash operator?

I wrote the code below to invert an upper triangular matrix, avoiding any possible multiplication/subtraction by zero. It just uses $\frac{1}{6}n^3+\ldots$ flops instead of $n^3+\ldots$ flops. ...
4
votes
2answers
369 views

LAPACK - singular matrices - what does the positive integer info mean?

please can you help me with my code - I use Lapack to solve complex matrix (quite biq) and do it in two steps: I call zgetrf (LU factorization) and then ...
4
votes
4answers
230 views

Determining the algorithmic complexity

A few of the iterative matrix algorithms (CG,GMRES etc.) I have authored are acting rather funny. They converge to the right answers but take abnormally long time to run. I am in the process of ...
4
votes
2answers
204 views

Fastest Way to Mutiply $10^4$ 2x2 Matrices

In a code that I work with (written in python, but also tagging as matlab because numpy is so close and I could use it if need be), we use a transfer matrix method to compute the properties of a ...
4
votes
1answer
121 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 ...
4
votes
3answers
4k views

debugging a rotation matrix for elastic constants

I have a transformation matrix which takes in the elastic constants from the local $rtl$ coordinates and then converts the elastic constants to the global $xyz$ coordinates via a rotation about the $z$...
4
votes
1answer
109 views

Finding the matrix inverse given a solver for the matrix equation $Ax=b$

So I'm given a solver that can solve for $x$ in the matrix equation $\underset{=}{A} \underline{x} = \underline{b}$ where $b$ can be anything we specify. (NB: A is an NxN matrix). I now want to find ...
4
votes
3answers
402 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 ...

1 2
3
4 5
11