// import visualization libraries {
const { Array2DTracer, Layout, LogTracer, Tracer, VerticalLayout, HorizonLayout } = require( 'algorithm-visualizer' );
// }
// define tracer variables {
const matrixTracer = new Array2DTracer( 'A (SPD)' );
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;
// 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 < i; ++j ) R[ i ].push( 0 );
for ( let j = i; j < N; ++j ) R[ i ].push( 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 = 0; 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 )
{
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 = 0; 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 );
// }
}
}