[vtk-developers] Additional math functionality

[Andrew Maclean]

What you are proposing here looks reasonable to me. I.e put the stand alone
methods in vtkMath and keep vtkPolynomialSystem separate. The only
reseervation I have is that, given that these are new routines and generally
not used throughout VTK and that vtkMath is used in a lot of places, will
the extra stuff adversely affect compilation/execution times?

As an aside, finally it is nice to see Bairstow's method appearing I always
thought it was a good general root finder. I remember ... converting it from
Fortran to C and writing all the complex math for it many years ago and
cursing C for not having something as simple as complex math on hand like
Fortran.


Andrew


-----Original Message-----
From: vtk-developers-bounces+a.maclean=cas.edu.au at vtk.org
[mailto:vtk-developers-bounces+a.maclean=cas.edu.au at vtk.org] On Behalf Of
Philippe P. Pebay
Sent: Friday, 4 November 2005 04:48
To: vtk-developers at vtk.org
Subject: Re: [vtk-developers] Additional math functionality

Yes. On our side, and at this point, we are talking about 3500 lines of our
code code, plus about
9000 lines from the homotopy-based polynomial system solver. Our code
pertains
to the following categories:

1. Stand-alone methods:
1.1 combinatorics (binomials, free combination, etc.) functions;
1.2 Stand-alone single-variable polynomial analytic real root snufflers.
These were mostly
    motivated by the fact that we only need real roots. Therefore, these
routines return only
    real-root related information. Another difference with the vtkMath root
snufflers is that
    ours return multiplicites -- because we needed them for our particular
application.
1.3 Stand-alone arbitrary order polynomial solver based on the Lin-Bairstow
method (synthetic
    quadratic division). Unlike Newton-type solvers, the Lin-Bairstow
algorithm goes after all
    roots (including complex ones). In our experience, it has been very
robust. Including
    for roots with high multiplicity.
1.4 Another stand-alone arbitrary (Day-Romero) solver, based on a more fancy
algorithm. This one
    is aimed at very large degree (tested with degree > 1000) polynomials.
We have not tested it
    as extensively as the previous one, though.

2. Then there is a more complex vtkPolynomialSystem class with a variety of
methods attached to
    it. It is aimed at handling, well... polynomial systems, expressed in
symbolic form. Among
    things that can be done with these systems is differentitation, variable
substitution,
    restriction to lower dimensional entities (e.g., restrict a 3D domain to
a plane using a
    parameterization), and also root finding. In the case of single-variable
systems, then a
    UnivariateSolver switches betweem the abovementioned solvers. For 2 and
3 variables, a
    BivariateSolver and a TrivariateSolver switch between linear solvers of
ours (that handle
    degenerate cases because we needed them as well, depending on the
dimensionality of the
    corresponding kernels) or, for nonlinear systems, call PSS. For the case
of nonlinear
    bivariate systems, we are also about to release a completely different
solver based on resultants.
    For more variables, then one has to always rely on PSS, because we did
not implement a generic
    n-dimensional linear solver method in vtkPolynomialSystem.

In my opinion, routines in 1. would fit right into vtkMath. Some renaming
could help figuring
out what, say, Cubic solver the user needs (multiplicities needed ? complex
roots needed ? etc.)

In the case of vtkPolynomialSystem, I think it makes sense to let it live by
itself (and by the way,
it relies on a 500-line long vtkPolynomialExpander class), as it is somewhat
less generic than the
stand-alone methods outlines in 1.

I'm looking forward to reading opinions about that. Thanks!
Philippe-

Will Schroeder wrote:
> There has been a request by several VTK developers to move some math 
> functionality into VTK (mainly polynomial root solvers). We are talking 
> several thousand lines of code. Of course we could just cram it into 
> vtkMath, take the ITK approach and include a math library, or create new 
> math classes, etc. At this point I am looking for opinions.
> 
> Will
> 
> _______________________________________________
> vtk-developers mailing list
> vtk-developers at vtk.org
> http://www.vtk.org/mailman/listinfo/vtk-developers
> 
> 


-- 
Philippe P. Pebay                |      pppebay at ca.sandia.gov
Sandia National Laboratories     |     Phone: +1 925 294 2024
PO Box 969, MS 9051              |     Cell : +1 925 784 3255
Livermore, CA 94550 U.S.A.       |     Fax  : +1 925 294 2595

_______________________________________________
vtk-developers mailing list
vtk-developers at vtk.org
http://www.vtk.org/mailman/listinfo/vtk-developers