Question

Suppose an \(n \times \left( {n + 1} \right)\) matrix is row reduced to reduced echelon form. Approximately what fraction of the total number of operations (flops) is involved in the backward phase of the reduction when \(n = 30\)? when \(n = 300\)?

Short answer

The fraction for \(n = 30\) is 0.048, and for \(n = 300\), it is 0.005.

Step-by-step solution

Define the general reduction to the echelon form of flops

It is known that \(\frac{{2{n^3}}}{3} + \frac{{{n^2}}}{2} - \frac{{7n}}{6}\) flops are required for the reduction to the echelon form for \(n \times \left( {n + 1} \right)\) matrix. If \(n\) is greater than or equal to 30, then there are approximately \(\frac{{2{n^3}}}{3}\) flops. Approximately \({n^2}\) flops are needed to reduce the echelon form further.

Obtain the number of flops for reduction

It is given that \(n = 30\). So, substitute 30 for \(n\) in \(\frac{{2{n^3}}}{3}\) to obtain the number of flops for \(n = 30\).

\(\begin{array}{c}\frac{{2{n^3}}}{3} = \frac{{2{{\left( {30} \right)}^3}}}{3}\\ = 18000\end{array}\)

Thus, when \(n = 30\) the reduction to echelon form takes 18,000 flops.

Obtain the number of flops for further reduction

Substitute 30 for \(n\) in \({n^2}\) to obtain the number of flops for \(n = 30\), for further reduction.

\(\begin{array}{c}{n^2} = {\left( {30} \right)^2}\\ = 900\end{array}\)

Thus, when \(n = 30\), the further reduction to echelon form takes 900 flops.

Evaluate the fraction of flops involved in the backward phase of reduction

The fraction involved with the backward phase is as shown below:

\(\frac{{900}}{{18000}} = 0.048\)

Obtain the number of flops for reduction

It is given that \(n = 300\). So, substitute 300 for \(n\) in \(\frac{{2{n^3}}}{3}\) to obtain the number of flops for \(n = 300\).

\(\begin{array}{c}\frac{{2{n^3}}}{3} = \frac{{2{{\left( {300} \right)}^3}}}{3}\\ = 18000000\end{array}\)

Thus, when \(n = 300\), the reduction to the echelon form takes 18,000,000 flops.

Obtain the number of flops for further reduction

Substitute 300 for \(n\) in \({n^2}\) to obtain the number of flops for \(n = 300\), for further reduction.

\(\begin{array}{c}{n^2} = {\left( {300} \right)^2}\\ = 90000\end{array}\)

Thus, when \(n = 300\), the further reduction to the echelon form takes 90,000 flops.

Evaluate the fraction of flops involved in the backward phase of reduction

The fraction involved with the backward phase is as shown below:

\(\frac{{90000}}{{18000000}} = 0.005\)

Thus, the fraction for \(n = 30\) is 0.048, and for \(n = 300\), it is 0.005.