Calculs de complexité relatifs à une méthode de dissection emboîtée

Résumé Nous présentons une numérotation de type Nested Dissection des inconnues d'un système linéaireAX=B pour des ensembles de matricescreuses symétriques définies positives correspondant à des famille de graphes non orientés,à degré borné, et admettant un -thérème de séparation. Comparativement aux méthodes et résultats de Rose [9], l'algorithme présenté est plus simple, mais les théorèmes de complexité moins généraux, en raison de l'hypothèse restrictive de degré borné. En outre, les démonstrations font appel en permanence à la structure d'arbre sur la famille des séparateurs qui constitue, par ailleurs, une partition de l'ensemble des sommets du graphe initial. Nous présentons ensuite le schéma général d'implémentation dans le cadre du code d'éléments finis MODULEF pourdes problèmes plans d'éléments finis, et nous donnons quelques mesures comparatives avec la numérotation plus classique qui tend à minimiser le profil de la matrice.

---

Complexity bounds for a nested dissection method

Summary A nested dissection ordering is given for solving any system of linear equationsAX=B, for the family ofsparse symmetric positive definite matrices corresponding to the class of undirected graphs withbounded degree, and satisfyinga -separator theorem. If we compare the methods and results presented by Rose [9], our algorithm is more simple, but the complexity results are less general because of the restriction of bounded degree. Besides, our proofs use continually the arborescent structure on the family of separators, which is, by another way, a partition of the set of vertices for the initial graph. Then, the general implementation scheme in the finite element package MODULEF, fortwo-dimensional finite element problems, is presented, and numerical comparisons between our ordering and the standard envelope method are given.

     

A discrete method of optimal control based upon the cell state space concept

A discrete method of optimal control is proposed in this paper. The continuum state space of a system is discretized into a cell state space, and the cost function is discretized in a similar manner. Assuming intervalwise constant controls and using a finite set of admissible control levels (u) and a finite set of admissible time intervals (), the motion of the system under all possible interval controls (u, ) can then be expressed in terms of a family of cell-to-cell mappings. The proposed method extracts the optimal control results from these mappings by a systematic search, culminating in the construction of a discrete optimal control table.The possibility of expressing the optimal control results in the form of a control table seems to give this method a means to make systems real-time controllable.Dedicated to G. LeitmannThe material is based upon work supported by the National Science Foundation under Grant No. MEA-82-17471. The author is also indebted to Professor G. Leitmann for his many helpful comments.     

Two families of mixed finite elements for second order elliptic problems

Summary Two families of mixed finite elements, one based on triangles and the other on rectangles, are introduced as alternatives to the usual Raviart-Thomas-Nedelec spaces. Error estimates inL ² () andH ^–5 () are derived for these elements. A hybrid version of the mixed method is also considered, and some superconvergence phenomena are discussed.     

Is Gauss quadrature optimal for analytic functions?

Summary We consider the problem of optimal quadratures for integrandsf: [–1,1] which have an analytic extension to an open diskD _r of radiusr about the origin such that 1 on . Ifr=1, we show that the penalty for sampling the integrand at zeros of the Legendre polynomial of degreen rather than at optimal points, tends to infinity withn. In particular there is an infinite penalty for using Gauss quadrature. On the other hand, ifr>1, Gauss quadrature is almost optimal. These results hold for both the worst-case and asymptotic settings.This research was supported in part by the National Science Foundation under Grants MCS-8203271 and MCS-8303111This research was supported in part by the National Science Foundation under Grant MCS-8923676     

The convergence of spline collocation for strongly elliptic equations on curves

Summary Most boundary element methods for two-dimensional boundary value problems are based on point collocation on the boundary and the use of splines as trial functions. Here we present a unified asymptotic error analysis for even as well as for odd degree splines subordinate to uniform or smoothly graded meshes and prove asymptotic convergence of optimal order. The equations are collocated at the breakpoints for odd degree and the internodal midpoints for even degree splines. The crucial assumption for the generalized boundary integral and integro-differential operators is strong ellipticity. Our analysis is based on simple Fourier expansions. In particular, we extend results by J. Saranen and W.L. Wendland from constant to variable coefficient equations. Our results include the first convergence proof of midpoint collocation with piecewise constant functions, i.e., the panel method for solving systems of Cauchy singular integral equations.Dedicated to Prof. Dr. Dr. h.c. mult. Lothar Collatz on the occasion of his 75th birthdayThis work was begun at the Technische Hochschule Darmstadt where Professor Arnold was supported by a North Atlantic Treaty Organization Postdoctoral Fellowship. The work of Professor Arnold is supported by NSF grant BMS-8313247. The work of Professor Wendland was supported by the Stiftung Volkswagenwerk     

Numerical solution of delay differential equations by uniform corrections to an implicit Runge-Kutta method

Summary In this paper we develop a class of numerical methods to approximate the solutions of delay differential equations. They are essentially based on a modified version, in a predictor-corrector mode, of the one-step collocation method atn Gaussian points. These methods, applied to ODE's, provide a continuous approximate solution which is accurate of order 2n at the nodes and of ordern+1 uniformly in the whole interval. In order to extend the methods to delay differential equations, the uniform accuracy is raised to the order 2n by some a posteriori corrections. Numerical tests and comparisons with other methods are made on real-life problems.This work was supported by CNR within the Progetto Finalizzato Informatica-Sottopr. P1-SOFMAT     

A three-dimensional quadratic nonconforming element

Summary We define a second-degree nonconforming element on tetrahedra. We build a basis for the opproximation space derived from this element. We prove a discrete regularity property similar to the one that holds for the corresponding two-dimensional element.This work was partly supported by NSERC and by the Ministère de l'Education du Québec     

Scaling properties of ℤ k- 1 actions on the circle

We derive universal scaling properties for ^k–1 actions on the circle whose generators have rotation numbers algebraic of degreek. As fork=2 these properties can be explained for arbitraryk in terms of a renormalization group transformation. It has at least one trivial fixed point corresponding to an action whose generators are pure rotations. The spectrum of the linearized transformation in this fixed point is analyzed completely. The fixed point is hyperbolic with a (k–1)-dimensional unstable manifold. In the casek=2 the known results are therefore recovered.     

Rapid and diverse route to natural product-like biaryl ether containing macrocycles

A two-step sequence involving an Ugi four-component reaction and an intramolecular nucleophilic aromatic substitution (S_NAr) has been developed for the rapid access to biaryl-ether containing macrocycles. In the course of this study, we documented that ammonium chloride can promote the Ugi-4CR in non-polar aprotic solvent (toluene) without the interference of an alternative Passerini reaction. Solid phase synthesis of macrocycles by this two-step sequence was also developed using polymer (Wang resin) supported α-(4′-fluoro-3′-nitro)phenethyl isocyanoacetate as one of the inputs.     

On constrained multivariate splines and their approximations

Summary The variational formulation of multivariate spline functions is generalized to include cases where the function has to satisfy inequality constraints such as positivity and convexity. Condition for existence and uniqueness of a solution is given. Approximation to the solution can be obtained by solving the variational problem in a finite dimensional subspace. Conditions for convergence and error estimates of the approximations are presented, both for interpolation problems and smoothing problems. The general theory is illustrated by specific examples including the volume-matching problem and the one-sided thin plate spline.This research is partially supported by the U.S. Army Contract No. DAAG 29-77-G-0207, and by NSF Grant No. MCS-8101836Part of this paper is based on Chapters 2 and 3 of the author's Ph. D. thesis. The author would like to express his sincere thanks to Professor Grance Wahba and to two referees for many helpful comments