Gaussian Elimination (LU Factorization)

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

// define tracer variables {
const matrixTracer = new Array2DTracer( 'A | I | b -> U | L | b (LU factorization)' );
const logTracer = new LogTracer( 'Console' );
Layout.setRoot( new VerticalLayout( [ matrixTracer, logTracer ] ) );
// }

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( '|' );
    for ( let j = 0; j < N; ++j )
    {
        if ( j === i ) matrix[ i ].push( 1 );
        else matrix[ i ].push( 0 );
    }
    matrix[ i ].push( '|' );
    matrix[ i ].push( Math.random() * ( 2 * random_range ) - random_range );
}
// }

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

for ( let k = 0; k < N - 1; ++k )
{
    // visualization {
    logTracer.println( 'Deal with column ' + k );
    // }
    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 )
    {
        matrix[ i ][ N + k + 1 ] = matrix[ i ][ k ] / matrix[ k ][ k ];
        matrix[ i ][ k ] = 0;
        // visualization {
        matrixTracer.select( i, k );
        matrixTracer.select( k, k );
        matrixTracer.patch( i, N + k + 1, matrix[ i ][ N + k + 1 ] );
        logTracer.println( 'L[' + i + '][' + k + '] = A[' + i + '][' + k + '] / A[' + k + '][' + k + ']' );
        Tracer.delay();
        matrixTracer.deselect( i, k );
        matrixTracer.deselect( k, k );
        matrixTracer.depatch( i, N + k + 1 );
        matrixTracer.patch( i, k, matrix[ i ][ k ] );
        logTracer.println( 'A[' + i + '][' + k + '] = 0' );
        Tracer.delay();
        matrixTracer.depatch( i, k );
        matrixTracer.select( i, N + k + 1 );
        // }
        for ( let j = k + 1; j < N; ++j )
        {
            matrix[ i ][ j ] -= matrix[ i ][ N + k + 1 ] * matrix[ k ][ j ];
            // visualization {
            matrixTracer.select( k, j );
            matrixTracer.patch( i, j, matrix[ i ][ j ] );
            logTracer.println( 'A[' + i + '][' + j + '] = A[' + i + '][' + j + '] - L[' + i + '][' + k + '] A[' + k + '][' + j + ']' );
            Tracer.delay();
            matrixTracer.deselect( k, j );
            matrixTracer.depatch( i, j );
            // }
        }
        matrix[ i ][ 2 * N + 2 ] -= matrix[ i ][ N + k + 1 ] * matrix[ k ][ 2 * N + 2 ];
        // visualization {
        matrixTracer.select( k, 2 * N + 2 );
        matrixTracer.patch( i, 2 * N + 2, matrix[ i ][ 2 * N + 2 ] );
        logTracer.println( 'b[' + i + '] = b[' + i + '] - L[' + i + '][' + k + '] b[' + k + ']' );
        Tracer.delay();
        matrixTracer.deselect( i, N + k + 1 );
        matrixTracer.deselect( k, 2 * N + 2 );
        matrixTracer.depatch( i, 2 * N + 2 );
        // }
    }
    // visualization {
    logTracer.println( 'Now we have desired U | L | b' );
    // }
}