Cholesky Factorization (Banded)

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

// define tracer variables {
const matrixTracer = new Array2DTracer( 'A (SPD, banded)' );
const RTRTracer = new Array2DTracer( 'R^T | R' );
const logTracer = new LogTracer( 'Console' );
Layout.setRoot( new VerticalLayout( [ RTRTracer, matrixTracer, logTracer ] ) );
// }

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

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

for ( let i = 0; i < N; ++i )
{
    // visualization {
    logTracer.println( 'Deal with row ' + i + ' of R' );
    // }
    RTR[ i ][ N + 1 + i ] = matrix[ i ][ i ];
    RTR[ i ][ i ] = RTR[ i ][ N + 1 + i ];
    // visualization {
    RTRTracer.patch( i, N + 1 + i, RTR[ i ][ N + 1 + i ] );
    RTRTracer.patch( i, i, RTR[ i ][ i ] );
    matrixTracer.select( i, i );
    logTracer.println( 'R[' + i + '][' + i + '] = A[' + i + '][' + i + ']' );
    Tracer.delay();
    RTRTracer.depatch( i, N + 1 + i );
    RTRTracer.depatch( i, i );
    matrixTracer.deselect( i, i );
    // }
    for ( let k = Math.max( 0, i - s ); k < i; ++k )
    {
        RTR[ i ][ N + 1 + i ] -= RTR[ k ][ N + 1 + i ] ** 2;
        RTR[ i ][ i ] = RTR[ i ][ N + 1 + i ];
        // visualization {
        RTRTracer.patch( i, N + 1 + i, RTR[ i ][ N + 1 + i ] );
        RTRTracer.patch( i, i, RTR[ i ][ i ] );
        RTRTracer.select( k, N + 1 + i );
        logTracer.println( 'R[' + i + '][' + i + '] = R[' + i + '][' + i + '] - (R[' + k + '][' + i + ']) ^ 2' );
        Tracer.delay();
        RTRTracer.depatch( i, N + 1 + i );
        RTRTracer.depatch( i, i );
        RTRTracer.deselect( k, N + 1 + i );
        // }
    }

    if ( RTR[ i ][ N + 1 + i ] <= 0 )
    {
        // visualization {
        Tracer.delay();
        logTracer.println( 'The algorithm stops because R[' + i + '][' + i + '] breaks down!' );
        // }
        break;
    }

    RTR[ i ][ N + 1 + i ] = Math.sqrt( RTR[ i ][ N + 1 + i ] );
    RTR[ i ][ i ] = RTR[ i ][ N + 1 + i ];
    // visualization {
    RTRTracer.patch( i, N + 1 + i, RTR[ i ][ N + 1 + i ] );
    RTRTracer.patch( i, i, RTR[ i ][ i ] );
    logTracer.println( 'R[' + i + '][' + i + '] = sqrt(R[' + i + '][' + i + '])' );
    Tracer.delay();
    RTRTracer.depatch( i, N + 1 + i );
    RTRTracer.depatch( i, i );
    // }

    for ( let j = i + 1; j < N && j <= i + s; ++j )
    {
        RTR[ i ][ N + 1 + j ] = matrix[ i ][ j ];
        RTR[ j ][ i ] = RTR[ i ][ N + 1 + j ];
        // visualization {
        RTRTracer.patch( i, N + 1 + j, RTR[ i ][ N + 1 + j ] );
        RTRTracer.patch( j, i, RTR[ j ][ i ] );
        matrixTracer.select( i, j );
        logTracer.println( 'R[' + i + '][' + j + '] = A[' + i + '][' + j + ']' );
        Tracer.delay();
        RTRTracer.depatch( i, N + 1 + j );
        RTRTracer.depatch( j, i );
        matrixTracer.deselect( i, j );
        // }
        for ( let k = Math.max( 0, j - s ); k < i; ++k )
        {
            RTR[ i ][ N + 1 + j ] -= RTR[ k ][ N + 1 + i ] * RTR[ k ][ N + 1 + j ];
            RTR[ j ][ i ] = RTR[ i ][ N + 1 + j ];
            // visualization {
            RTRTracer.patch( i, N + 1 + j, RTR[ i ][ N + 1 + j ] );
            RTRTracer.patch( j, i, RTR[ j ][ i ] );
            RTRTracer.select( k, N + 1 + i );
            RTRTracer.select( k, N + 1 + j );
            logTracer.println( 'R[' + i + '][' + j + '] = R[' + i + '][' + j + '] - R[' + k + '][' + i + '] * R[' + k + '][' + j + ']' );
            Tracer.delay();
            RTRTracer.depatch( i, N + 1 + j );
            RTRTracer.depatch( j, i );
            RTRTracer.deselect( k, N + 1 + i );
            RTRTracer.deselect( k, N + 1 + j );
            // }
        }
        RTR[ i ][ N + 1 + j ] /= RTR[ i ][ N + 1 + i ];
        RTR[ j ][ i ] = RTR[ i ][ N + 1 + j ];
        // visualization {
        RTRTracer.patch( i, N + 1 + j, RTR[ i ][ N + 1 + j ] );
        RTRTracer.patch( j, i, RTR[ j ][ i ] );
        RTRTracer.select( i, N + 1 + i );
        logTracer.println( 'R[' + i + '][' + j + '] = R[' + i + '][' + j + '] / R[' + i + '][' + i + ']' );
        Tracer.delay();
        RTRTracer.depatch( i, N + 1 + j );
        RTRTracer.depatch( j, i );
        RTRTracer.deselect( i, N + 1 + i );
        // }
    }
}