[vtk-developers] Additional math functionality

[Philippe P. Pebay]

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