Recall that when we solve a large linear system, we often use Gaussian elimination followed by backward substitution. Gaussian elimination converts an n × n linear system into an upper triangular linear system by using the "row operations":
• Add a multiple of one row to another row
• Swap two rows
• Multiply one row by a nonzero constant
An upper triangular system has zeroes below the "diagonal" extending from the upper left-hand corner to the lower right-hand corner.
For example, the linear system
2x₀ - 3x₁ = 3
4x₀ - 5x₁ + x₂ = 7
2x₀ - x₁ - 3x₂ = 5
can be reduced to the upper triangular form
2x₀ - 3x₁ = 3
x₁ + x₂ = 1
-5x₂ = 0

and this system can be easily solved by first finding x₂ using the last equation, then finding x₁ using the second equation, and finally finding x₀ using the first equation.

We can devise a couple of serial algorithms for back substitution. The "row-oriented" version is
for (row = n-1: row >= 0; row --) {
x[row] = b[row];
for (col = row+1; col < n; col++)
x[row] -= A[row][col]*x[col];
x[row] /= A[row][row];
}

Here the "right-hand side" of the system is stored in array b, the two-dimensional array of coefficients is stored in array A, and the solutions are stored in array x. An alternative is the following "column-oriented" algorithm:
for (row = n-1: row >= 0; row --) {
x[row] = b[row];

for (col = n-1; col >= 0; col--) {
x[col] /= A[col][col];
for (row = 0; row < col; row++)
x[row] -= A[row][col]*x[col];
}

a. Determine whether the outer loop of the row-oriented algorithm can be parallelized.