Problem Statement
How much computational time does it take to conduct the forward elimination part of the Naïve Gauss Elimination method on a square matrix?
This post is brought to you by
- Holistic Numerical Methods Open Course Ware:
- Numerical Methods for the STEM undergraduate at http://nm.MathForCollege.com;
- Introduction to Matrix Algebra for the STEM undergraduate at http://ma.MathForCollege.com
- the textbooks on
- the Massive Open Online Course (MOOCs) available at
Thank you for the lectures Dr. Kaw, this brings back great memories.
Nice post, many times you hear the cost is O(n^3) but can easily forget why or what the lower order terms are.
One thing that comes to mind is that this is true as long as the computation is arithmetically intense. That is, the number of floating point operations to memory accesses is large. In the case of Gaussian elimination, this is true and so counting FLOPS is a good measure of cost. However, in a operation such as a sparse matrix-vector product (where you have low arithmetic intensity, 1 fused multiply-add per memory access) it is the memory bandwidth that limits performance.
Nice post, we are often reminded that the cost is O(n^3) but often forget why or what the lower order terms are.
One things that comes to mind is that modeling the FLOPS is a good measure of performance only if the computation has a high arithmetic intensity. That is, the number of floating point operations to memory accesses is high. This is true of Gaussian Elimination. However, in an operation such as a sparse matrix-vector multiply the arithmetic intensity is low (1 fused multiply add per memory access) and the operation becomes bandwidth limited.
Yes, so true Nate. This may be very rudimentary way to introduce students to computational time. Many variables enter into the equation for computational time as you pointed out! Watch soon for computational time for Gauss Jordan method of finding inverse!