PYRAMID ALGORITHMS FOR BERNSTEIN-Bé ZIER FINITE ELEMENTS OF HIGH, NONUNIFORM ORDER IN ANY DIMENSION

摘要

The archetypal pyramid algorithm is the de Casteljau algorithm, which is a standard tool for the evaluation of Bézier curves and surfaces. Pyramid algorithms replace an operation on a single high order polynomial by a recursive sequence of self-similar affine combinations, and are ubiquitous in computer aided geometric design for computations involving high order curves and surfaces. Pyramid algorithms have received no attention whatsoever from the high (or low) order finite element community. We develop and analyze pyramid algorithms for the efficient handling of all of the basic finite element building blocks, including the assembly of the element load vectors and element stiffness matrices. The complexity of the algorithm for generating the element stiffness matrix is optimal. A new, nonuniform order, variant of the de Casteljau algorithm is developed that is applicable to the variable polynomial order case but incurs no additional complexity compared with the original algorithm. The work provides the methodology that enables the efficient use of a completely general distribution of polynomial degrees without any restriction in changes between adjacent cells, in any number of spatial dimensions.