Gaussian Elimination Complete Pivoting (GECP)

// import visualization libraries {
const { Array2DTracer, Layout, LogTracer, Tracer, VerticalLayout, HorizonLayout } = require( 'algorithm-visualizer' );
// }

// define tracer variables {
const matrixTracer = new Array2DTracer( 'A | b (reduce to an upper triangluar matrix, GECP)' );
const logTracer = new LogTracer( 'Console' );
Layout.setRoot( new VerticalLayout( [ matrixTracer, logTracer ] ) );
// }

const FULL_COMPARSION = false; // set true to see full comparsions
const random_range = 3;
const N = 8;
// initialization {
const matrix = [];
for ( let i = 0; i < N; ++i )
{
    matrix.push( [] );
    for ( let j = 0; j < N; ++j ) matrix[ i ].push( Math.random() * ( 2 * random_range ) - random_range );
    matrix[ i ].push( '|' );
    matrix[ i ].push( Math.random() * ( 2 * random_range ) - random_range );
    matrix[ i ].push( '' );
    matrix[ i ].push( 'x' + i );
    matrix[ i ].push( '' );
    matrix[ i ].push( '' );
    matrix[ i ].push( '' );
}
// }

// visualization {
matrixTracer.set( matrix );
Tracer.delay();
// }

for ( let k = 0; k < N - 1; ++k )
{
    // visualization {
    logTracer.println( 'Make desired zeros in column ' + k );
    // }
    let pivot_row_index = k;
    let pivot_column_index = k;
    // visualization {
    if ( FULL_COMPARSION )
    {
        matrixTracer.select( pivot_row_index, pivot_column_index );
        logTracer.println( 'Initial pivot index is (' + pivot_row_index + ', ' + pivot_column_index + ')' );
    }
    // }
    for ( let i = k + 1; i < N; ++i )
    {
        // visualization {
        if ( FULL_COMPARSION )
        {
            logTracer.println( 'Compare A[' + pivot_row_index + '][' + pivot_column_index + '] and A[' + pivot_row_index + '][' + i + ']' );
            matrixTracer.select( pivot_row_index, i );
            Tracer.delay();
        }
        // }
        if ( Math.abs( matrix[ pivot_row_index ][ pivot_column_index ] ) < Math.abs( matrix[ pivot_row_index ][ i ] ) )
        {
            // visualization {
            if ( FULL_COMPARSION )
            {
                matrixTracer.deselect( pivot_row_index, pivot_column_index );
                logTracer.println( 'Current pivot index is changed to (' + pivot_row_index + ', ' + i + ')' );
            }
            // }
            pivot_column_index = i;
        }
        else
        {
            // visualization {
            if ( FULL_COMPARSION )
            {
                matrixTracer.deselect( pivot_row_index, i );
                logTracer.println( 'Pivot index remains the same' );
            }
            // }
        }
        // visualization {
        if ( FULL_COMPARSION )
        {
            Tracer.delay();
        }
        // }
    }
    for ( let j = k + 1; j < N; ++j )
    {
        for ( let i = k; i < N; ++i )
        {
            // visualization {
            if ( FULL_COMPARSION )
            {
                logTracer.println( 'Compare A[' + pivot_row_index + '][' + pivot_column_index + '] and A[' + j + '][' + i + ']' );
                matrixTracer.select( j, i );
                Tracer.delay();
            }
            // }
            if ( Math.abs( matrix[ pivot_row_index ][ pivot_column_index ] ) < Math.abs( matrix[ j ][ i ] ) )
            {
                // visualization {
                if ( FULL_COMPARSION )
                {
                    matrixTracer.deselect( pivot_row_index, pivot_column_index );
                    logTracer.println( 'Current pivot index is changed to (' + j + ', ' + i + ')' );
                }
                // }
                pivot_row_index = j;
                pivot_column_index = i;
            }
            else
            {
                // visualization {
                if ( FULL_COMPARSION )
                {
                    matrixTracer.deselect( j, i );
                    logTracer.println( 'Pivot index remains the same' );
                }
                // }
            }
            // visualization {
            if ( FULL_COMPARSION )
            {
                Tracer.delay();
            }
            // }
        }
    }
    // visualization {
    if ( FULL_COMPARSION )
    {
        matrixTracer.deselect( pivot_row_index, pivot_column_index );
    }
    else
    {
        logTracer.println( 'Pivot index is (' + pivot_row_index + ', ' + pivot_column_index + ')' );
        matrixTracer.select( k, k );
        matrixTracer.select( pivot_row_index, pivot_column_index );
        Tracer.delay();
        matrixTracer.deselect( k, k );
        matrixTracer.deselect( pivot_row_index, pivot_column_index );
    }
    // }
    let flag_changed = false;
    if ( pivot_row_index !== k )
    {
        // visualization {
        flag_changed = true;
        logTracer.println( 'Swap row ' + k + ' and row ' + pivot_row_index );
        // }
        for ( let i = 0; i < N; ++i )
        {
            const temporary_swap_value = matrix[ k ][ i ];
            matrix[ k ][ i ] = matrix[ pivot_row_index ][ i ];
            matrix[ pivot_row_index ][ i ] = temporary_swap_value;
            // visualization {
            matrixTracer.patch( k, i, matrix[ k ][ i ] );
            matrixTracer.patch( pivot_row_index, i, matrix[ pivot_row_index ][ i ] );
            // }
        }
        const temporary_swap_value = matrix[ k ][ N + 1 ];
        matrix[ k ][ N + 1 ] = matrix[ pivot_row_index ][ N + 1 ];
        matrix[ pivot_row_index ][ N + 1 ] = temporary_swap_value;
        // visualization {
        matrixTracer.patch( k, N + 1, matrix[ k ][ N + 1 ] );
        matrixTracer.patch( pivot_row_index, N + 1, matrix[ pivot_row_index ][ N + 1 ] );
        Tracer.delay();
        for ( let i = 0; i < N; ++i )
        {
            matrixTracer.depatch( k, i );
            matrixTracer.depatch( pivot_row_index, i );
        }
        matrixTracer.depatch( k, N + 1 );
        matrixTracer.depatch( pivot_row_index, N + 1 );
        // }
    }
    if ( pivot_column_index !== k )
    {
        // visualization {
        flag_changed = true;
        logTracer.println( 'Swap column ' + k + ' and column ' + pivot_column_index );
        // }
        for ( let i = 0; i < N; ++i )
        {
            const temporary_swap_value = matrix[ i ][ k ];
            matrix[ i ][ k ] = matrix[ i ][ pivot_column_index ];
            matrix[ i ][ pivot_column_index ] = temporary_swap_value;
            // visualization {
            matrixTracer.patch( i, k, matrix[ i ][ k ] );
            matrixTracer.patch( i, pivot_column_index, matrix[ i ][ pivot_column_index ] );
            // }
        }
        const temporary_swap_value = matrix[ k ][ N + 3 ];
        matrix[ k ][ N + 3 ] = matrix[ pivot_column_index ][ N + 3 ]
        matrix[ pivot_column_index ][ N + 3 ] = temporary_swap_value;
        // visualization {
        matrixTracer.patch( k, N + 3, matrix[ k ][ N + 3 ] );
        matrixTracer.patch( pivot_column_index, N + 3, matrix[ pivot_column_index ][ N + 3 ] );
        Tracer.delay();
        for ( let i = 0; i < N; ++i )
        {
            matrixTracer.depatch( i, k );
            matrixTracer.depatch( i, pivot_column_index );
        }
        matrixTracer.depatch( k, N + 3 );
        matrixTracer.depatch( pivot_column_index, N + 3 );
        // }
    }
    if ( ! flag_changed )
    {
        // visualization {
        logTracer.println( 'There is no need to swap rows or columns' );
        Tracer.delay();
        // }
    }
    if ( Math.abs( matrix[ k ][ k ] ) < 1e-6 )
    {
        // visualization {
        Tracer.delay();
        logTracer.println( 'The algorithm stops because the pivot value is too small!' );
        // }
        break;
    }
    for ( let i = k + 1; i < N; ++i )
    {
        const multiplier = matrix[ i ][ k ] / matrix[ k ][ k ];
        matrix[ i ][ k ] = 0;
        // visualization {
        matrixTracer.select( i, k );
        matrixTracer.select( k, k );
        matrixTracer.patch( i, N + 5, 'm =' );
        matrixTracer.patch( i, N + 6, multiplier );
        logTracer.println( 'm = A[' + i + '][' + k + '] / A[' + k + '][' + k + ']' );
        logTracer.println( 'm = ' + multiplier );
        Tracer.delay();
        matrixTracer.deselect( i, k );
        matrixTracer.deselect( k, k );
        matrixTracer.depatch( i, N + 5 );
        matrixTracer.depatch( i, N + 6 );
        matrixTracer.patch( i, k, matrix[ i ][ k ] );
        logTracer.println( 'A[' + i + '][' + k + '] = 0' );
        Tracer.delay();
        matrixTracer.depatch( i, k );
        matrixTracer.select( i, N + 6 );
        // }
        for ( let j = k + 1; j < N; ++j )
        {
            matrix[ i ][ j ] -= multiplier * matrix[ k ][ j ];
            // visualization {
            matrixTracer.select( k, j );
            matrixTracer.patch( i, j, matrix[ i ][ j ] );
            logTracer.println( 'A[' + i + '][' + j + '] = A[' + i + '][' + j + '] - m A[' + k + '][' + j + ']' );
            Tracer.delay();
            matrixTracer.deselect( k, j );
            matrixTracer.depatch( i, j );
            // }
        }
        matrix[ i ][ N + 1 ] -= multiplier * matrix[ k ][ N + 1 ];
        // visualization {
        matrixTracer.select( k, N + 1 );
        matrixTracer.patch( i, N + 1, matrix[ i ][ N + 1 ] );
        logTracer.println( 'b[' + i + '] = b[' + i + '] - m b[' + k + ']' );
        Tracer.delay();
        matrixTracer.deselect( i, N + 6 );
        matrixTracer.deselect( k, N + 1 );
        matrixTracer.depatch( i, N + 1 );
        matrixTracer.patch( i, N + 5, '' );
        matrixTracer.patch( i, N + 6, '' );
        matrixTracer.depatch( i, N + 5 );
        matrixTracer.depatch( i, N + 6 );
        // }
    }
}