Gaussian Elimination (Doolittle)

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

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

const random_range = 3;
const N = 8;
// initialization {
const matrix = [];
const LU = [];
for ( let i = 0; i < N; ++i )
{
    LU.push( [] );
    for ( let j = 0; j < N; ++j ) LU[ i ].push( 0 );
    LU[ i ].push( '|' );
    for ( let j = 0; j < N; ++j ) LU[ i ].push( 0 );
    matrix.push( [] );
    for ( let j = 0; j < N; ++j ) matrix[ i ].push( Math.random() * ( 2 * random_range ) - random_range );
}
// }

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

for ( let k = 0; k < N; ++k )
{
    LU[ k ][ k ] = 1;
    // visualization {
    LUTracer.patch( k, k, LU[ k ][ k ] );
    logTracer.println( 'L[' + k + '][' + k + '] = 1' );
    Tracer.delay();
    LUTracer.depatch( k, k );
    // }
}

for ( let k = 0; k < N; ++k )
{
    // visualization {
    logTracer.println( 'Compute row ' + k + ' of U' );
    // }
    for ( let j = k; j < N; ++j )
    {
        LU[ k ][ N + 1 + j ] = matrix[ k ][ j ];
        // visualization {
        LUTracer.patch( k, N + 1 + j, LU[ k ][ N + 1 + j ] );
        matrixTracer.select( k, j );
        logTracer.println( 'U[' + k + '][' + j + '] = A[' + k + '][' + j + ']' );
        Tracer.delay();
        LUTracer.depatch( k, N + 1 + j );
        matrixTracer.deselect( k, j );
        // }
        for ( let p = 0; p < k; ++p )
        {
            LU[ k ][ N + 1 + j ] -= LU[ k ][ p ] * LU[ p ][ N + 1 + j ];
            // visualization {
            LUTracer.patch( k, N + 1 + j, LU[ k ][ N + 1 + j ] );
            LUTracer.select( k, p );
            LUTracer.select( p, N + 1 + j );
            logTracer.println( 'U[' + k + '][' + j + '] = U[' + k + '][' + j + '] - L[' + k + '][' + p + '] * U[' + p + '][' + j + ']' );
            Tracer.delay();
            LUTracer.depatch( k, N + 1 + j );
            LUTracer.deselect( k, p );
            LUTracer.deselect( p, N + 1 + j );
            // }
        }
    }

    if ( Math.abs( LU[ k ][ N + 1 + k ] ) < 1e-6 )
    {
        // visualization {
        Tracer.delay();
        logTracer.println( 'The algorithm stops because U[' + k + '][' + k + '] is too small!' );
        // }
        break;
    }

    // visualization {
    logTracer.println( 'Compute column ' + k + ' of L' );
    // }
    for ( let i = k + 1; i < N; ++i )
    {
        LU[ i ][ k ] = matrix[ i ][ k ];
        // visualization {
        LUTracer.patch( i, k, LU[ i ][ k ] );
        matrixTracer.select( i, k );
        logTracer.println( 'L[' + i + '][' + k + '] = A[' + i + '][' + k + ']' );
        Tracer.delay();
        LUTracer.depatch( i, k );
        matrixTracer.deselect( i, k );
        // }
        for ( let p = 0; p < k; ++p )
        {
            LU[ i ][ k ] -= LU[ i ][ p ] * LU[ p ][ N + 1 + k ];
            // visualization {
            LUTracer.patch( i, k, LU[ i ][ k ] );
            LUTracer.select( i, p );
            LUTracer.select( p, N + 1 + k );
            logTracer.println( 'L[' + i + '][' + k + '] = L[' + i + '][' + k + '] - L[' + i + '][' + p + '] * U[' + p + '][' + k + ']' );
            Tracer.delay();
            LUTracer.depatch( i, k );
            LUTracer.deselect( i, p );
            LUTracer.deselect( p, N + 1 + k );
            // }
        }
        LU[ i ][ k ] /= LU[ k ][ N + 1 + k ];
        // visualization {
        LUTracer.patch( i, k, LU[ i ][ k ] );
        LUTracer.select( k, N + 1 + k );
        logTracer.println( 'L[' + i + '][' + k + '] = L[' + i + '][' + k + '] / U[' + k + '][' + k + ']' );
        Tracer.delay();
        LUTracer.depatch( i, k );
        LUTracer.deselect( k, N + 1 + k );
        // }
    }
}