================================================================================
MRFI: Multivariate Rational Function Interpolation
Black box solver for parametric linear systems over Q
================================================================================

OVERVIEW
--------
This package solves systems  A(y) x = b(y) where the entries of A and b are
polynomials in parameters y = (y1, ..., yn) and returns the solution
x_i(y) = N_i(y) / D_i(y) as exact rational functions over Q.

The algorithm is black box i.e., it never builds the full symbolic matrix.
It evaluates the system over a prime field at a sequence of points, runs a
univariate rational function reconstruction along an affine line, recovers
multivariate monomials with a Zippel style transposed Vandermonde solve and then
lifts the result from Z_p back to Q with integer rational reconstruction.

REQUIREMENTS (At minimum) 
-------------------------
 - Linux on x86-64 (Our C++ backend uses x86-64 assembly).
 - g++ with C++11 support.
 - Maple 2018 or later.

FILES TO DOWNLOAD
-----------------
You require four files. Please put them all in the same directory.

 main.cpp              C++ backend (Newton interp,Vandermonde solve,
                       Berlekamp Massey and Rational reconstruction).
 int128g.c             128-bit integer math. Roman Pearce,CECM/SFU 2015
                       (included by main.cpp).
 mapleWrapper.mpl      Maple bindings for the C++ routines (cppNewtonInterp,
                       cppVS,cppBMM,cppRR).
 solver.mpl            MRFI solver.

BUILD
-----
From the directory where you placed the four files run the following
commands in your terminal.

 $ g++ -O3 main.cpp -o test
 $ g++ -O3 -shared -fPIC -o cppObj.so main.cpp

Verify the shared object was indeed produced.

 $ ls -l cppObj.so

If the compile errors mention `__int128` or inline assembly then your compiler
is not x86-64. Please note that this code will not build on ARM/PowerPC without porting the
int128g.c routines.

CONFIGURE
---------
Open mapleWrapper.mpl in any editor. The first line reads

  libObj := "/cecm/home/mss59/Desktop/.../cppObj.so":

Replace that path with the absolute path to the cppObj.so you just built.
This is the only line you need to change.

QUICK START — 4x4 SYMMETRIC TOEPLITZ EXAMPLE
--------------------------------------------
In a Maple session run from the same directory:

 > read "exampleT4.mpl":

This builds a 4x4 symmetric Toeplitz system  T x = b  where
T_{ij} = y_{|i-j|+1} and b_i = 1, treats {y1, y2, y3, y4} as symbolic
parameters, solves it with MRFI (the black box method) and writes the results
in a file called "resultsT4.txt". 

OUTPUT
------
solver.mpl produces:

 - resultsTN.txt: detailed per-n report including
      * BB calls,term counts and recovered solution vector.

CONFIGURATION OPTIONS IN solver.mpl
---------------------------------
Near the top of the driver:

 n_min, n_max          range of system sizes to test.
 do_verify             if true, also solves with LinearAlgebra:-LinearSolve
                       and checks MRFI output matches.
 do_ffge               if true, also runs FFGE for comparison.
 n_ffge_max            skip FFGE entirely for n > this value (FFGE memory
                       usage grows super polynomially. The default is set to 12).

TROUBLESHOOTING
---------------
"Error, (in define_external) unable to load library libObj.so"
   The path in mapleWrapperv2.mpl is wrong. Use an absolute path and
   not a relative one.

"Error, (in MRFI) ... matrix is singular"
   Try a different prime or rerun the random affine line direction
   may have hit a degenerate sample.

"Cannot allocate enough memory" during FFGE
   Expected for n >= 13 on symmetric Toeplitz. Set n_ffge_max := 12 (or
   lower) in solver.mpl. MRFI will continue running for larger n.

"ITERATION ERROR n=NN" appears in stdout
   The outer try/catch caught a failure in iteration n=NN. The sweep
   continues with the next n. Check resultsTN.txt for what completed.

CONTACT
-------
[Mantej Sokhi: mss59@sfu.ca]