Skip to content

MATLAB/OCTAVE functions for the Polynomial Numerical Linear Algebra Framework

License

LGPL-3.0, GPL-3.0 licenses found

Licenses found

LGPL-3.0
COPYING.LESSER
GPL-3.0
COPYING
Notifications You must be signed in to change notification settings

lawrenceccheung/PNLA_MATLAB_OCTAVE

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

31 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Polynomial Numerical Linear Algebra package for Matlab©/Octave©

Multi-functional package for solving all kinds of problems with multivariate polynomials in double precision.

Author: Kim Batselier

  1. Basics

Only 1 monomial ordering is supported: the degree negative lex ordering. This graded ordering is defined for two n-variate monomials x^a and x^b as

a > b

if

|a| = \sum_i^n a_i > |b| = \sum_i^n b_i or

|a|=|b| and the leftmost nonzero entry of a-b is negative.

In this definition x^a stands for

x^a = x_1^a_1 * x_2^a_2 * ... * x_n^a_n,

where a is an n-tuple of nonnegative integers.

A system of s multivariate polynomials is represented by an s-by-2 cell. The first column elements are vectors containing the coefficients. The second column elements are matrices containing the corresponding exponents. For example, the system

f_1 = 5.3 x_1^2 + 9 x_2 x_3 -1,
f_2 = 2 x_1^3 + .5 x_2^2 - 7.89 x_3 - 94,
f_3 = x_1 - 2.13,

is represented by

polysys{1,1}=[5.3,9,-1]
polysys{1,2}=[2 0 0;0 1 1;0 0 0]
polysys{2,1}=[2,.5,-7.89,-94]
polysys{2,2}=[3 0 0;0 2 0;0 0 1;0 0 0]
polysys{3,1}=[1,-2.13]
polysys{3,2}=[1 0 0;0 0 0]

  1. Available functions

This is an incomplete list of all available functions. Most functions have more input and output arguments than specified here. Type 'help X' in MATLAB/OCTAVE to get a full description of the function X.

  • index = feti(exponent)

Converts an exponent to its corresponding linear index with respect to the degree negative lex ordering. If the exponent argument is a matrix of exponents, then feti() is applied to each row of the matrix.

  • exponent = fite(index,n)

Converts a linear index with respect to the degree negative lex ordering to the corresponding n-variate exponent.

  • d0 = getD0(polysys)

Returns the maximal total degree of the given polynomial system.

  • dorig = getDorig(polysys)

dorig(i) (i=1:s) contains the maximal total degree of the multivariate polynomial corresponding with polysys[i,1],polysys[i,2].

  • [p,q] = getMDim(polysys,d)

Returns the number of columns p and the number of rows q of the Macaulay matrix of degree d.

  • [M nzmax] = getM(polysys,d,sparseM)

Returns the Macaulay matrix of degree d for the given polynomial system polysys. sparseM is an optional boolean variable, set to 1 to use a column compressed data structure to store the matrix, default sparseM is 0.

  • Mex = getMex(polysys,d,dmin,sparseM)

Returns the extra rows that need to be added to M(dmin) in order to construct M(d). Suitable for recursive updating of M.

  • [q r] = polyDiv(psys,polysys)

Polynomial division of a multivariate polynomial psys by a set of multivariate divisors polysys, computed using oblique projections. Returns the coefficient vectors of the quotient q and remainder r.

  • [a b R] = candecomp(polysys,d)

Computes the canonical decomposition of the vector space of n-variate polynomials up to degree d for a given polynomial system polysys. Vectors a and b contain the indices of the linearly independent and dependent monomials (degree negative lex ordered). Each row of R is a coefficient vector of a reduced polynomial.

  • [a b R] = rcandecomp(polysys,d)

Computes the reduced canonical decomposition of the vector space of n-variate polynomials up to degree d for a given polynomial system polysys. Vectors a and b contain the indices of the reduced linearly independent and dependent monomials (degree negative lex ordered).

  • [p d] = elim(polysys,var)

Returns the coefficient vector of a polynomial p that lies in the ideal spanned by the polynomials in polysys and from which all variables var are eliminated. Var is a a vector of indices, e.g. suppose n=5 and var=[1,2,5] then p will be a polynomial in the variables x3 and x4.

  • puni = punivar(polysys,var)

Returns the univariate (in the variable var) polynomial puni that lies in the polynomial ideal generated by polysys.

  • [dp dm] = aln(polysys,dmax)

Analyzes the left null space of the Macaulay matrix of polysys up to a degree dmax. The variables dp and dm contains the degrees of the binomial coefficients that generate the Hilbert Function. Each entry k of dp contributes a term nchoosek(d-k+n,n) to the Hilbert Function and likewise -nchoosek(d-k+n,n) for an entry of dm.

  • [lcm h] = getLCM(fsys,gsys,tol)

Returns the approximate least common multiple (lcm) of two given polynomials fsys and gsys. Also the factor h such that lcm = g*h is calculated. The optional variable tol is to decide when a principal angle is numerically zero.

  • [gcd e] = getGCD(psys,qsys,tol)

Returns the approximate greatest common divisor (gcd) of two given polynomials psys and qsys. The optional variable tol is to decide when a principal angle is numerically zero.

  • [Nnew tol] = updateN(N,M,sparse)

Updates the numerical kernel N of M(d) using the recursive orthogonalization theorem. M contains the rows that need to be added to M(d) to form M(d+1).

  • [Unew Nnew tol] = updateOrth(U,N,M,sparse)

Updates the numerical basis for the row space U and kernel N of M(d) using the recursive orthogonalization theorem. M contains the rows that need to be added to M(d) to form M(d+1).

  • [root d c ns check cr digits] = qdsparf(polysys)

Quick & Dirty Sparse Affine Root-Finding algorithm. Uses SuiteSparseQR. Computes all affine roots of a given polynomial system polysys.

  • [root d c ns check cr digits] = sparf(polysys)

Sparse affine root-finding algorithm. Try the quick & dirty algorithm first, it will be faster.

About

MATLAB/OCTAVE functions for the Polynomial Numerical Linear Algebra Framework

Resources

License

LGPL-3.0, GPL-3.0 licenses found

Licenses found

LGPL-3.0
COPYING.LESSER
GPL-3.0
COPYING

Stars

Watchers

Forks

Packages

No packages published

Languages

  • MATLAB 100.0%