linearalgebra.lib

//######################## linearalgebra.lib ######################################
// A library of linear algebra functions. Its official prefix is `la`.
//
// This library adds some new linear algebra functions:
// 
// `determinant`
//
// `minor`
//
// `inverse`
//
// `transpose2`
//
// `matMul` matrix multiplication
//
// `identity`
//
// `diag`
// 
// How does it work? An `NxM` matrix can be flattened into a bus `si.bus(N*M)`. These buses can be passed to functions as long as `N` and sometimes `M` (if the matrix need not be square) are passed too.
// 
// #### Some things to think about going forward
// 
// ##### Implications for ML in Faust
// 
// Next step of making a "Dense"/"Linear" layer from machine learning.
// Where in the libraries should `ReLU` go?
// What about 3D tensors instead of 2D matrices? Image convolutions take place on 3D tensors shaped `HxWxC`.
//
// #####Design of matMul
// 
// Currently the design is `matMul(J, K, L, M, leftHandMat, rightHandMat)` where `leftHandMat` is `JxK` and `rightHandMat` is `LxM`.
// 
// It would also be neat to have `matMul(J, K, rightHandMat, L, M, leftHandMat)`.
// 
// Then a "packed" matrix could be consistently stored as a combination of a 2-channel "header" `N, M` and the values `si.bus(N*M)`.
// 
// This would ultimately enable `result = packedLeftHand : matMul(packedRightHand);` for the equivalent numpy code: `result = packedLeftHand @ packedRightHand;`.
// 
// #### References
// * <https://github.com/grame-cncm/faustlibraries/blob/master/linearalgebra.lib>
//#################################################################################

/************************************************************************
************************************************************************
FAUST library file
Copyright (C) 2003-2024 GRAME, Centre National de Creation Musicale
----------------------------------------------------------------------
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as
published by the Free Software Foundation; either version 2.1 of the
License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

EXCEPTION TO THE LGPL LICENSE : As a special exception, you may create a
larger FAUST program which directly or indirectly imports this library
file and still distribute the compiled code generated by the FAUST
compiler, or a modified version of this compiled code, under your own
copyright and license. This EXCEPTION TO THE LGPL LICENSE explicitly
grants you the right to freely choose the license for the resulting
compiled code. In particular the resulting compiled code has no obligation
to be LGPL or GPL. For example you are free to choose a commercial or
closed source license or any other license if you decide so.
************************************************************************
************************************************************************/

ba = library("basics.lib");
si = library("signals.lib");
ro = library("routes.lib");

declare name "Faust Linear Algebra Library";
declare version "0.1.0";


//-----------`(la.)determinant`-------------------------
// Calculates the determinant of a bus that represents
// an `NxN` matrix.
//
// #### Usage
// ```
// si.bus(N*N) : determinant(N) : _
// ```
//
// Where:
//
// * `N`: the size of each axis of the matrix.
//------------------------------------------------------
determinant(1) = _;
determinant(2) = det2x2
with {
    det2x2(a, b, c, d) = a * d - b * c;
};
determinant(N) = si.bus(N*N) <: sum(i, N, ((-1)^i) * ba.selector(i, N*N) * minor(N, 0, i));
declare determinant author "David Braun";
declare determinant copyright "MIT License";


//-----------`(la.)minor`----------------------------------------------------
// An utility for finding the matrix minor when inverting a matrix.
// It returns the determinant of the submatrix formed by deleting the row at
// index `ROW` and column at index `COL`.
// The following implementation doesn't work but looks simple.
// ```
// minor(N, ROW, COL) = par(r, N, par(c, N, select2((ROW==r)||(COL==c),_,!))) : determinant(N-1);
// ```
//
// #### Usage
// ```
// si.bus(N*N) : minor(N, ROW, COL) : _
// ```
// 
// Where:
//
// * `N`: the size of each axis of the matrix.
// * `ROW`: the selected position on 0th dimension of the matrix (`0 <= ROW < N`)
// * `COL`: the selected position on the 1st dimension of the matrix (`0 <= COL < N`)
//
// #### References
// * <https://en.wikipedia.org/wiki/Minor_(linear_algebra)#First_minor>
//----------------------------------------------------------------------------
minor(N, ROW, COL) = par(i, ROW, deleteColumn), deleteRow, par(i, N-1-ROW, deleteColumn) : determinant(N-1)
with {
    deleteColumn = si.bus(COL), !, si.bus(N-1-COL);
    deleteRow = par(i, N, !);
};
declare minor author "David Braun";
declare minor copyright "MIT License";


//-----------`(la.)inverse`---------------------------------------------
// Inverts a matrix. The incoming bus represents an `NxN` matrix.
// Note, this is an unsafe operation since not all matrices are invertible.
//
// #### Usage
// ```
// si.bus(N*N) : inverse(N) : si.bus(N*N)
// ```
// 
// Where:
//
// * `N`: the size of each axis of the matrix.
//---------------------------------------------------------------------
inverse(1) = 1/_;
inverse(2) = inverse2x2
with {
    inverse2x2(a, b, c, d) = si.vecOp(((d, -b, -c, a), detBus), /)
    with {
        detBus = (a*d-b*c) <: si.bus(4);
    };
};
inverse(N) = si.bus(N*N) <: si.vecOp((adjugate(N), detBus), /)
with {
    detBus = determinant(N) <: si.bus(N*N);
    adjugate(N) = si.bus(N*N) <: par(i, N * N, cofactorTranspose(N, i));
    cofactorTranspose(N, i) = (-1)^(ROW + COL) * minor(N, ROW, COL)
    with {
        ROW = floor(i / N);
        COL = i % N;
    };
};
declare inverse author "David Braun";
declare inverse copyright "MIT License";


//--------------`(la.)transpose2`-----------------------------------
// Transposes an `NxM` matrix stored in row-major order, resulting
// in an `MxN` matrix stored in row-major order.
//
// #### Usage
// ```
// si.bus(N*M) : transpose2(N, M) : si.bus(M*N)
// ```
// 
// Where:
//
// * `N`: the number of rows in the input matrix
// * `M`: the number of columns in the input matrix
//-----------------------------------------------------------------
transpose2(N, M) = ro.interleave(M,N);
declare transpose2 author "David Braun";
declare transpose2 copyright "MIT License";


//--------------`(la.)matMul`---------------------------------------------
// Multiply a `JxK` matrix (mat1) and an `LxM` matrix (mat2) to produce a `JxM` matrix.
// Note that `K==L`.
// Both matrices should use row-major order.
// In terms of numpy, this function is `mat1 @ mat2`.
//
// #### Usage
// ```
// matMul(J, K, L, M, si.bus(J*K), si.bus(L*M)) : si.bus(J*M)
// ```
// 
// Where:
//
// * `J`: the number of rows in `mat1`
// * `K`: the number of columns in `mat1`
// * `L`: the number of rows in `mat2`
// * `M`: the number of columns in `mat2`
//-----------------------------------------------------------------
matMul(J, K, L, M) = si.bus(J*K), transpose2(L, M) <: par(j, J, par(m, M,
    si.dot(K, (ba.selectbus(K, J, j)), (ba.selectbus(L, M, m)))
));
declare matMul author "David Braun";
declare matMul copyright "MIT License";


//---------------`(la.)identity`-------------------------
// Creates an `NxN` identity matrix.
//
// #### Usage
// ```
// identity(N) : si.bus(N*N)
// ```
// 
// Where:
//
// * `N`: The size of each axis of the identity matrix.
//-------------------------------------------------------
identity(N) = par(i, N, par(j, N, i == j));
declare identity author "David Braun";
declare identity copyright "MIT License";


//---------------`(la.)diag`-------------------------------
// Creates a diagonal matrix of size `NxN` with specified
// values along the diagonal.
//
// #### Usage
// ```
// si.bus(N) : diag(N) : si.bus(N*N)
// ```
// 
// Where:
//
// * `N`: The size of each axis of the matrix.
//---------------------------------------------------------
diag(N) = route(N, N*N, par(i,N, (i+1, (N+1)*i+1)));
declare diag author "David Braun";
declare diag copyright "MIT License";