# Can you give me a mathematical estimation about the algorithm complexity of matrix multiplication and matrix inversion in MATLAB?

8 visualizaciones (últimos 30 días)
Blue Bird el 16 de Jul. de 2017
Editada: Walter Roberson el 16 de Jul. de 2017
Can you give me a mathematical estimation about the algorithm complexity of matrix multiplication and matrix inversion in MATLAB?
If matrix A is m*n, matrix B is n*k and the number of thread is s, the algorithm complexity of matrix multiplication is something like o (m, n, k, s). If A is n*n, what is the algorithm complexity of matrix inversion (inv(A) or A\B)?
I hope the algorithm complexity of MATLAB is not business secret. It is better be a published paper.
##### 0 comentariosMostrar -2 comentarios más antiguosOcultar -2 comentarios más antiguos

Iniciar sesión para comentar.

Walter Roberson el 16 de Jul. de 2017
Editada: Walter Roberson el 16 de Jul. de 2017
The mtimes operator does not attempt any of the theoretic reductions as those take a bunch of time and memory. The complexity order for m by n * n by k is expected to be m * n * p
For larger matrices, MATLAB calls upon BLAS Level 3 routines. For practical reasons, the lowest theoretical operation count is not necessarily the most efficient implementation: actual implementations must take into account cache behavior, and might be able to take advantage of hardware SIMD (Single Instruction Multiple Data) operations. See the discussion at https://stackoverflow.com/questions/1303182/how-does-blas-get-such-extreme-performance
Likewise time complexity of matrix inversion is O(n^3) in practice.
The number of threads does not change the operation complexity. I have not studied the algorithms to see how portions are divided up between threads. Block algorithms make a substantial practical difference. Because of the effect of hardware SIMD and instruction pipelining and caching, modeling the time complexity of actual matrix multiplication is fairly tricky, and cannot be reduced down to (m, n, p, s)
##### 0 comentariosMostrar -2 comentarios más antiguosOcultar -2 comentarios más antiguos

Iniciar sesión para comentar.

### Categorías

Más información sobre Code Generation en Help Center y File Exchange.

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!