Hot answers tagged

66 votes
Accepted

why is A*v+B*v faster than (A+B)*v?

Except for code which does a significant number of floating-point operations on data that are held in cache, most floating-point intensive code is performance limited by memory bandwidth and cache ...
user avatar
27 votes
Accepted

Why do we usually not want the eigenvalues of non-symmetric matrices?

Stability under perturbations Let $E$ be a perturbation such that $\|E\| \leq \varepsilon$. If $A$ is symmetric, then the eigenvalues of $A+E$ are at a distance $\varepsilon$ from those of $A$. (Bauer-...
user avatar
21 votes
Accepted

In FEM, why is the stiffness matrix positive definite?

The property follows from the property of the corresponding (weak form of the) partial differential equation; this is one of the advantages of finite element methods compared to, e.g., finite ...
user avatar
21 votes

why is A*v+B*v faster than (A+B)*v?

Your code is limited by memory bandwidth. For trivial math, it's often better to count memory accesses rather than flops. You'll get the following table: ...
user avatar
  • 346
19 votes

Robust algorithm for $2 \times 2$ SVD

See https://math.stackexchange.com/questions/861674/decompose-a-2d-arbitrary-transform-into-only-scaling-and-rotation (sorry, I would have put that in a comment but I've registered just to post this ...
user avatar
18 votes

Rule of thumb for sparse vs dense matrix storage

For what it is worth, for random sparse matrices of size 10,000 by 10,000 vs. dense matrices of the same size, on my Xeon workstation using MATLAB and Intel MKL as the BLAS, the sparse matrix-vector ...
user avatar
18 votes
Accepted

How to find the nearest/a near positive definite from a given matrix?

Quick sketch of an answer for the Frobenius norm: Replace $X$ with the closest symmetric matrix, $Y=\frac12 (X+X^\top)$. Take an eigendecomposition $Y=QDQ^\top$, and form the diagonal matrix $D_+=\...
user avatar
14 votes
Accepted

Super C++ optimization of matrix multiplication with Armadillo

In fundamental C++, I find the problem here is that C++ will allocate a new object of cx_mat to store evolutionMatrix*stateMatrix, and then copy the new object to stateMatrix with operator=(). I ...
user avatar
  • 11.4k
14 votes
Accepted

What is the fastest algorithm for computing the inverse matrix and its determinant for positive definite symmetric matrices?

For problems I am interested in, the matrix dimension is 30 or less. As WolfgangBangerth notes, unless you have a large number of these matrices (millions, billions), performance of matrix inversion ...
user avatar
14 votes

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

Here is a quick example which is very practical related to memory usage in PDEs. When one discretizes the Laplace operator, $\Delta u$, for example, in the Heat Equation $$ u_t = \Delta u + f(t,u) .$$...
user avatar
14 votes

Matrix multiplication accuracy Matlab vs Python

Here is R1, as computed in MATLAB: ...
user avatar
14 votes

Matrix multiplication accuracy Matlab vs Python

First, see Mark L. Stone's answers, which is completely correct. Second, realize that this is the reason why people told you to use relative errors in your numerical analysis class. :) Third, the ...
user avatar
13 votes
Accepted

Numerically stable approach for calculating x in Ax=b

If the solution of $Ax=b$ is unstable, the matrix is very ill-conditioned (i.e., has a very large condition number), and (paraphrasing Lanczos) no amount of mathematical trickery can make it stable. ...
user avatar
13 votes
Accepted

Beating typical BLAS libraries matrix multiplication performance

Consolidating the comments: No, you are very unlikely to beat a typical BLAS library such as Intel's MKL, AMD's Math Core Library, or OpenBLAS.1 These not only use vectorization, but also (at least ...
13 votes
Accepted

Rule of thumb for sparse vs dense matrix storage

All matrix operations are memory bound (and not compute bound) on today's processors. So basically, you have to ask which format stores fewer bytes. This is easy to compute: For a full matrix, you ...
user avatar
12 votes
Accepted

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

It is true that compilers are getting better and better at auto-vectorization, and for basic coefficient-wise operations like 2*A-4*B a library like Eigen cannot do ...
user avatar
  • 666
12 votes
Accepted

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

Normally there are some principal reasons to prefer solve a linear system respect to use the inverse. Briefly: problem with the conditional number (@GoHokies comment) problem in the sparse case (@...
user avatar
12 votes

Checking singularity of a matrix

If you can compute products with $A$ and $A^T$, as you specify in a comment, you can run the classical sparse SVD algorithms such as scipy.sparse.linalg.svds, ...
user avatar
11 votes

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

MATLAB's \ (aka mldivide) command does not blindly compute the inverse of the matrix. Instead, it uses one of several algorithms ...
user avatar
11 votes
Accepted

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

First: there is a must read on this topic Moler, Cleve, and Charles Van Loan. "Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later." SIAM review 45.1 (2003): 3-49. ...
user avatar
  • 1,728
11 votes
Accepted

Do I really need to invert this matrix

Since $$ A = B(I-B)^{-1} = (I-B)^{-1}(I-B)B(I-B)^{-1} = (I-B)^{-1}B(I-B)(I-B)^{-1} =(I-B)^{-1}B $$ So you want to solve $$ (I-B)A=B $$ You seem to need only the first three columns of $A$. Solve the ...
user avatar
  • 2,983
10 votes

Robust algorithm for $2 \times 2$ SVD

@Pedro Gimeno "I doubt it can be any more robust than that." Challenge accepted. I noticed the usual approach is to use trig functions like atan2. Intuitively, there shouldn't be a need to use trig ...
user avatar
10 votes
Accepted

Fast vector - "diagonal" matrix multiplication

This can be interpreted as summing over an index of a tensor when the vector $x$ is reshaped into a box of numbers instead of a list. In particular, if $X$ is the $d\text{-by-}d$ folded version of $x$,...
user avatar
  • 3,013
10 votes

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

The question is ill-posed -- you don't say what you mean by "desirable" or "superior". If a phenomenon I try to model involves only real numbers, then clearly using real matrices is the better way. On ...
user avatar
10 votes
Accepted

Method to check for positive definite matrices

The standard way of approaching this is really to attempt a Cholesky factorization and check to see if such a factorization exists. This is both fast and realiable. Here it is in MATLAB notation: A ...
user avatar
  • 2,139
9 votes

Does the "cofactor technique" for inverting a matrix have any practical significance?

I'm going against the crowd - the adjugate matrix is in fact very useful for some specialty applications with small dimensionality (like four or less), in particular when you need the inverse of a ...
user avatar
9 votes
Accepted

Compute all eigenvalues of a very big and very sparse adjacency matrix

You can use the shift-invert spectral transform [1] and compute the spectrum band by band. The technique is also explained in my article [2]. Besides the implementation in [1], an implementation is ...
user avatar
  • 2,185
9 votes
Accepted

Convexity of Sum of $k$-smallest Eigenvalue

Given $A \in {\bf S}^n$ (a positive definite matrix) with eigenvalues $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n $, then: $\displaystyle f_k(A)=\sum_{i=1}^{k} \lambda_i$ is concave. Why? $$...
user avatar
  • 2,096
9 votes
Accepted

Efficiently computing $e^{tX}$ for many different values of $t$

An anti-Hermitian matrix is diagonalizable, with orthogonal eigenvectors (ref). Hence you can write $X = PDP^{-1}$, where $D$ is a diagonal matrix. Therefore the exponential can be calculated as $e^X=...
user avatar
  • 254
8 votes

Robust algorithm for $2 \times 2$ SVD

I needed an algorithm that has little branching (hopefully CMOVs) no trigonometric function calls high numerical accuracy even with 32 bit floats We want to calculate $c_1, s_1, c_2, s_2, \sigma_1$ ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible