[vtk-developers] Additional math functionality

[Philippe P. Pebay]

Andrew Maclean wrote:
> 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?
No. We already use routines from both vtkMath and vtkSnlMath in our code, with
no compilation nor execution problems. For instance, vtkPolynomialSystem relies on both.
Therefore, moving some routines from vtkSnlMath into vtkMath should not be a problem.
> 
> 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.
I agree, Lin-Bairstow rocks! And what's always possible, to further improve
the quality of the approximate solutions, is to polish the roots found by LB by feeding them
as initial guesses into a couple of Newton iterations.

P.



> 
> 
> 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