ICS Theory Group

ICS 269, Winter 2000: Theory Seminar


5 May 2000:
Fast Evaluation Of Tensor Product Hypersurfaces
Mac Casale, ICS, UC Irvine

The speaker, being under time pressure from upcoming exams, retreats to the security of his roots in solid modeling - this time, however, from the point of view of looking for lower bounds and efficient, practical implementations of tensor products of polynomials. The context is CAD/CAE, which has various representations for solid objects. At issue is the efficient evaluation of geometric objects known as tensor product surfaces and hypersurfaces. A hypersurface is shown to be a tensor product of polynomials, which can be written in various forms, depending on choice of basis vectors in the linear space of polynomial coefficients. This leads to the question of efficiency of evaluating the tensor product form. We mention the industrial context, followed by a review of lower bounds on polynomial evaluation and show how these stack-up with traditional tensor product evaluation methods. This is followed by some extensions. The talk ends with a working session structured around four different potential approaches.