[  Download   ]   [ Table of Contents ]   [ Key features  ]  [ Publications  ]     [  Contact   ]    [  About  ]

!!! This website is under updating

NAClab -- Numerical Algebraic Computing Toolbox for Matlab
Copyright © 2012 by Zhonggang Zeng.  All rights reserved.  Updated on March 18, 2016

Unique capabilities:  Accurate numerical solutions of hypersensitive algebraic problems from approximate data
                                   Intuitive polynomial computation interface in Matlab
                                   Soving linear equation  L(z) = b directly from linear transformation L even if it is rank-deficient, without matrix input from the use.

NAClab features convenient WYSIWYG polynomial  input, output and manipulations, solving linear equations directly from linear transformations, and solving nonlinear least squares problem with Gauss-Newtion iterations.

NAClabe consists of  three components:

Featured modules:     Solving polynomial systems, Jordan Canonical Forms, multiplicities of nonlinear systemspolynomial GCD and factorizations, ....
Research toolbox:       Generic linear equation solver without matrices, Gauss-Newton iteration, ....
Software building blocks  [Link]

NAClab a joint research project in development by Tien-Yien Li at Michigan State University and Zhonggang Zeng at Northeastern Illinois University. supported by National Science Foundation under grants DMS-1115587,  DMS-0715127 and DMS-0412003. It is an expansion from its predecessor Apalab (and its Maple counterpart is  ApaTools).  Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.  Disclaimer:   NAClab is an on-going research project,  Bugs and shortcomings likely exist.  The authors are not responsible for any damage  or loss from using this software. Users should verify their results through whatever means.

Project leaders:   Tien-Yien Li  and  Zhonggang Zeng  (Contact via email:  zzeng at  neiu dot edu )
Colaborators/contributors:  Liping Chen, Tianran Chen, Wenrui Hao, Tsung-Lin Lee, Wenyuan Wu, Andrew Sommese

!!!New!!!Solving linear equations  L(z) = b  
                - directly from linear transformation L without representation matrix
                - including homogeneous equation  L(z) = 0  
                - 
even if  L is rank-deficient  

NAClab can directly solve a general linear equation   L(z) = b  for its general numerical solution  where L is a linear transformation between (products) of vector spaces. As a special case, the module LinearSolve solves L(z) = 0 for the numerical kernel.    [ detained manual for LinearSolve ]

A general numerical solution within an error tolerance is in the form of  z = z0 + c1*z1+...+ck*zk  where z0 is the minimum norm solution, c1,..,ck are constants and {z1,...,zk} forms a basis for the numerical kernel of L within the error tolerance

For a demo, NAClab outputs polynomials f and g  such that    p f + q g  = u   where  p, q  are given polynomials of degrees m and n  respectivly and  u = GCD(p,q) of degree k. In other words, NAClab solves the linear equation
                             L(f,g)  = u
where   L
is the linear transformation defined by  L(f,g)  = p f + q g  with fixed parameters p, q.  Users do not need to provide representation matrices for the linear transformations unless they choose to do so.  NAClab generates representation matrices internally. 

The complete process for this example is as follows

Write an m-file that implement the linear transformation and save it as an Matlab function:

function Z = map2gcd(f,g,p,q)

    Z = pplus(ptimes(p,f),ptimes(q,g));

Enter polynomials f, g, u as character strings, provide the domain and parameter for the linear transformation:

>> f = '5.99999 - 9*x + 3*x^3 - 4*x^4 + 6*x^5 - 2*x^7';
>> g = '-2 + 5*x - 3*x^2 - x^3 + x^4 + 2*x^5 - 3.00002*x^6 + x^8';
>> u = '2-2.99999*x+1.00001*x^3';
>> domain = {'1+x+x^2+x^3+x^4+x^5','1+x+x^2+x^3+x^4'};
>> parameter = {f,g};

Just like that, we are ready to call LinearSolve with error tolerance 1e-4

>> [Z,K,lcond,res] = LinearSolve({@map2gcd,domain,parameter}, u, 1e-4);

The minimum norm solution:

>> Z

Z =

    '0.315213638005548 + 0.0325895733429298*x + 0.021703…'     '-0.054358027177057 + 0.0434095337991119*x + 0.10852…'

The numerical kernel within the error tolerance 1e-4:

>> K{:}

ans =

    '0.249999389461494 - 0.250001189336557*x - 0.2500021…'     '0.74999762066815 - 0.500002203566776*x^4'


 !!!New!!!Solving polynomial systems
             by the homotopy method based on HOM4PS

Polynomials systems can be solved  for numerical solutions in a straightforward and intuitive setting.  For example: To solve the following polynomial system with 20 zeros

     -x^5 + y^5 - 3*y - 1 = 0
     5*y^4-3                    = 0
      -20*x+y-z                = 0

simply call "psolve" with straitforward input [ more details ]

>> P = {'-x^5+y^5-3*y-1','5*y^4-3','-20*x+y-z'};  % define the polynomial system

>> [Solutions, variables] = psolve(P)             % call the polynomial system solver

   Solutions =

     Column 1

     0.778497746685646 + 0.893453081179308i
    -0.000000000000000 + 0.880111736793394i
   -15.569954933712914 -16.988949886792764i

     ... ...

     Column 20

     0.778497746685646 - 0.893453081179308i
     0.000000000000000 - 0.880111736793393i
   -15.569954933712925 +16.988949886792767i


   variables =

    'x'    'y'    'z'


New!!! Direct polynomial manipulation:  

(Symbolic Math Toolbox is not needed, except for multiplicity computation of nonlinear systems other than polynomials)
Polynomials can now be entered and shown as character strings, such as  
   >> f = '3*x^2 - (2-5i)*x^3*y^4 - 1e-3*z^5-6.8'
   >> g = '-2*y^3 - 5*x^2*z + 8.2'

Using polynomials strings as input, users can now perform common polynomial operations  such as addition, multiplication, power, evaluation, differentiation, factorization, extracting coefficients, finding greatest common divison (GCD), by calling NAClab functions, such as
   >> p = PolynomialPlus('2*x^5-3*y','4+x*y')     % add any number of polynomials
   >> q = PolynomialTimes(f,g,h)  % multiply any number of polynomials
   >> v = PolynomialEvaluate(f,{'x','z'},[3,4]) % evaluate f(x,y,z) for x=3, z=4
and a lot more.  For example, to compute a greatest common divisor:

   >> f = '10 - 5*x^2*y + 6*x*y^2 - 3*x^3*y^3';
   >> g = '30 + 10*y + 18*x*y^2 + 6*x*y^3'
   >> u = PolynomialGCD(f,g)
   u =
   33.5410196624968 + 20.1246117974981*x*y^2

 KeyKey features:

The functions for
are major development in both algorithm design and software implementations. For instance, the univariate factorization is based on an award winning paper on accurate computation of multiple roots

Table of contents


List of functions:

     Functions are in three categories:  Queck-access functions,  Programming tools for polynomial compuations,  and  Matrix compuation tools

Quick-access polynomial functions:

Functions in this category accept input polynomials as character strings, such as
   >> f = '3*x^2 - (2-5i)*x^3*y^4 - 1e-3*z^5-6.8'
   >> g = '-2*y^3 - 5*x^2*z + 8.2'

A list of quick access functions are as follows.  Use, say >> help GetVariables, to access documentations.  Many functions have shortened aliases. For example, pvar is an alias for GetVariables.  

Programming tools for polynomial computations:

Functions in this category are designed for experts for developing algorithms and implementations for numerical polynomial algebra. These functions requires polynomials represented as either a coefficient matrix or a coefficient vector.  

A univariate polynomial is represented by its coefficient vector.  For example,  f(x) = x3 + 2x2 + 3x + 4  is represented as
               >> f  =  [1, 2, 3, 4]   % or  its transpose

An  m-multivariate polynomial  of  n  terms is represented by a coefficient matrix  of size  (m+1) by  n  according to the following rules:
     1.  Every column of  F  represents one term (monomial)
     2.  F(i,j)    for i<m+1   is the exponent of the i-th variable on j-th term
     3.  F(m+1,j)  is the coefficient of the j-th term
For example, let    p(x, y, z)  =  8.5  +  (3-2i)x3 y  +  5 x2 z5   -  2 y3   + 6 y3 z2  .   Users can transform its string representation to coefficient matrix representation by calling the quick access function PolynString2CoefMat :  
   >> f = '8.5 + (3-2i)*x^3*y + 5*x^2*z^5 - 2*y^3 + 6*y^3*z^2';
   >> F = PolynString2CoefMat(f,{'x','y','z'})
   F =

        0     3.0000                     0          0     2.0000         
        0     1.0000                3.0000     3.0000          0         
        0          0                     0     2.0000     5.0000         
   8.5000     3.0000 - 2.0000i     -2.0000     6.0000     5.0000     

The following are a list of expert functions as software building blocks

Matrix computation functions

Relevant publications

               Computing multiple roots of inexact polynomials,  Z. Zeng,   Mathematics of Computation, 74(2005),  pp 869 - 903
                               Algorithm 835: MultRoot -- A Matlab package for computing polynomial roots and multiplicities, Z. Zeng,  ACM Transaction on Mathematical Software, 30(2004), pp 218-315
                   
Multiple zeros of nonlinear systems  ,   B.H. Dayton, T.-Y. Li and Z. Zeng,  Mathematics of Computation, (80)2011, pp. 2143-2168
                   
The numerical factorization of polynomials   W. Wu and Z. Zeng, Foundations of Computational Mathmatics, DOI 10.1007/s10208-015-9289-1          
                    
Sensitivity and computation of a defective eigenvalue    Z. Zeng,  preprint,   [Resources / Matlab codes]  
                    
Regularization and matrix computation in numerical polynomial algebra   Z. Zeng,
                Mixed volume  computation. A revisit   T.-L. Lee  and T..-Y. Li
                    
HOM4PS-2.0:  A software package for solving polynomial systems by the polyhedral homotopy continuation method   T.-L. Lee,  T..-Y. Li and C.-H. Tsai  
                   
Algorithm 931: An algorithm and software for computing multiplicity structure at zeros of nonlinear systems,  W. Hao, A.J. Sommese and Z. Zeng,  ACM TOMS
                   
ApaTools:  A software toolbox for approximate polynomial algebra
Zhonggang Zeng,  in Software for Algebraic Geometry,  IMA Volume 148, M.S. Stillman et al. eds.,  Springer,  pp149-167,  2008


Modules with brief explanations and examples

LinearSolve

LinearSolve is designed to solve linear equations in the form of
                        L(z) = b
for its general numerical solution where L : V -> W is a linear transformation between vector spaces V and W.

The main difference between LinearSolve and conventional linear system solver are as follows
   (i) The linear transformation L does not need to be a matrix, and the matrix representation of L is not needed.
   (ii) The solution z can be a column vector, a matrix, a polynomial, or an array of matrices and polynomials.
   (iii) LinearSolve solves the homogeneous equation L(z) = 0 for the numrical kernel of L.
   (iv) The linear transformation L is allowed to be (numerically) rank-deficient. In such cases the solution is in the form of
z = z0 + c1*z1+...+ck*zk  where z0 is the minimum norm solution, c1,..,ck are arbitrary constants and {z1,...,zk} forms a basis for the numerical kernel of L within the error tolerance.

Syntax:      >> [Z, K, lcond, res] = LinearSolve( {@L, Domain, parameters}, b, tol)

To solve  L(z) = b with LinearSolve, the user needs to provide 4 crucial input items:
   (a)  A Matlab function m-file that carries out the linear transformation L from imput z and parameters
   (b)  The domain of the linear transformation L
   (c)  The parameters of the linear transformation L
   (d)  an error tolerance (optional,  with default value ||L||*1e-10)