Computational Time for Forward Elimination Steps of Naive Gaussian Elimination on a Square Matrix

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?

CTdecomposition

This post is brought to you by

0 thoughts on “Computational Time for Forward Elimination Steps of Naive Gaussian Elimination on a Square Matrix”

  1. 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.

  2. 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.

    1. 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!

Leave a Reply