A package for manipulation of dense multivariate polynomials. Contains routines for:
There is now a small C library of functions which mirror the Lisp routines. These will allow inter-operation between the nice and easy to use Lisp front-end and a more efficient C library for operations if speed is required.
To use the C library, first make it using the provided Makefile See examples/ffi-example.lisp and libfpoly/fpoly_test.c for an example of it in use.
Create polynomial objects with the (make-fpoly
(defvar p (make-fpoly '(x y) 2)) in X,Y of degree 2
(setf (fpoly-coeff poly 1 1) 2) set the coeff in front of the XY term to 2
There is a reader macro defined for convenience, #{ },
allowing entering of human readable format polynomials, e.g.
#{1 + 2x^2} -> 1 + 2X^2 equivalent to (make-fpoly 'X 2 '(1 0 2))
Note that the parser can only cope with single-character variable names.
This is due to the ambiguity of terms like "xyz", is this equal to multplying three variables,
X, Y, Z or two variables XY, Z etc. If long names are required then they have to be set
by a substitute call, e.g. we want 1 + FOO^2 so we do
(princ (fpoly-substitute 'x 'foo #{1 + 2x^2})) 1 + 2*X^2
Note also that the parser is robust enough to cope with nested subexpressions, e.g.
#{x(1 + y)} -> X + XY
There are functions for the standard arithmetic operations addition (fpoly-add) subtraction (fpoly-sub), multiplication (fpoly-mul) and also exponentiation (fpoly-expt).
Use these just like the standard functions + - * expt, e.g.
(fpoly-add #{1 + x^2} #{1 - y^2}) -> 2 + X^2 - Y^2
There are also other functions for evaluation, substitution and simplification of polynomials
Matrices of polynomials are used to represent systems of linear equations with polynomial coefficients. These can be loaded from files using (load-matrix "filename").
For testing purposes you can define a random system using the macro
(def-test-system (matrix-name values-name) variables max-degree max-coeff n &key entry-density coeff-density vals)
This will define an n x n system of equations with density (probability of being non-zero) entry-density. The coefficients in the randomly generated polynomials have a density also.
E.g. define a nice and simple test system
(def-test-system (mymat myvals) '(x y) 3 10 3 :vals '(1 2 3))
This defines using defparameter a matrix called mymat and a set of values (solution to the system of equations) myvals, in this case '(1 2 3). If not specified then they will be random.
There are three approaches to solving.
This will, using the standard operationss fpoly-add etc., transform the input matrix into upper triangular form and then solve for each of the system values, if possible.
So with the above system (which we know to have a solution of '(1 2 3)) we get
(direct-solve mymat) -> (#{1} #{2} #{3})
The advantage being that the matrix operations involve matrices of bignums only rather than polynomials.
At present, solve-system does not work.
The function lagrange-interpolate computes a polynomial which goes through a set of points.
This requires finding the determinant of a set of n x n matrices which can grow very large for even moderately sized input problems. Here, n = (base-offset nvars degree). Be warned, this requires finding determinants of large matrices and will therefore become very slow very quickly!
A set of CFFI bindings to the partner C library are also provided. The functions provided by the C library are a subset of those available in Lisp; it should be used only where speed is desired (and even then should be tested to ensure it really is faster). Lisp is the lead platform.
Frank James