Efficient Collocation Schemes for Singular Boundary Value Problems

We discuss an error estimation procedure for the global error of collocation schemes applied to solve singular boundary value problems with a singularity of the first kind. This a posteriori estimate of the global error was proposed by Stetter in 1978 and is based on the idea of Defect Correction, originally due to Zadunaisky. Here, we present a new, carefully designed modification of this error estimate which not only results in less computational work but also appears to perform satisfactorily for singular problems. We give a full analytical justification for the asymptotical correctness of the error estimate when it is applied to a general nonlinear regular problem. For the singular case, we are presently only able to provide computational evidence for the full convergence order, the related analysis is still work in progress. This global estimate is the basis for a grid selection routine in which the grid is modified with the aim to equidistribute the global error. This procedure yields meshes suitable for an efficient numerical solution. Most importantly, we observe that the grid is refined in a way reflecting only the behavior of the solution and remains unaffected by the unsmooth direction field close to the singular point.     

Constructing Invariant Fairness Measures for Surfaces

The paper proposes a rational method to derive fairness measures for surfaces. It works in cases where isophotes, reflection lines, planar intersection curves, or other curves are used to judge the fairness of the surface. The surface fairness measure is derived by demanding that all the given curves should be fair with respect to an appropriate curve fairness measure. The method is applied to the field of ship hull design where the curves are plane intersections. The method is extended to the case where one considers, not the fairness of one curve, but the fairness of a one parameter family of curves. Six basic third order invariants by which the fairing measures can be expressed are defined. Furthermore, the geometry of a plane intersection curve is studied, and the variation of the total, the normal, and the geodesic curvature and the geodesic torsion is determined.     

Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.