Overlapping Schwarz and Spectral Element Methods for Linear Elasticity and Elastic Waves

The classical overlapping Schwarz algorithm is here extended to the spectral element discretization of linear elastic problems, for both homogeneous and heterogeneous compressible materials. The algorithm solves iteratively the resulting preconditioned system of linear equations by the conjugate gradient or GMRES methods. The overlapping Schwarz preconditioned technique is then applied to the numerical approximation of elastic waves with spectral elements methods in space and implicit Newmark time advancing schemes. The results of several numerical experiments, for both elastostatic and elastodynamic problems, show that the convergence rate of the proposed preconditioning algorithm is independent of the number of spectral elements (scalability), is independent of the spectral degree in case of generous overlap, otherwise it depends inversely on the overlap size. Some results on the convergence properties of the spectral element approximation combined with Newmark schemes for elastic waves are also presented.     

Augmenting Trees to Meet Biconnectivity and Diameter Constraints

Given a graph G=(V,E) and a positive integer D , we consider the problem of finding a minimum number of new edges E' such that the augmented graph G'=(V,E\cup E') is biconnected and has diameter no greater than D. In this note we show that this problem is NP-hard for all fixed D , by employing a reduction from the DOMINATING SET problem. We prove that the problem remains NP-hard even for forests and trees, but in this case we present approximation algorithms with worst-case bounds 3 (for even D ) and 6 (for odd D ). A closely related problem of finding a minimum number of edges such that the augmented graph has diameter no greater than D has been shown to be NP-hard by Schoone et al. [21] when D=3 , and by Li et al. [17] when D=2. Received April 19, 1999; revised June 5, 2001.     

New two‐dimensional slope limiters for discontinuous Galerkin methods on arbitrary meshes

In this paper, we introduce an extension of Van Leer's slope limiter for two‐dimensional discontinuous Galerkin (DG) methods on arbitrary unstructured quadrangular or triangular grids. The aim is to construct a non‐oscillatory shock capturing DG method for the approximation of hyperbolic conservative laws without adding excessive numerical dispersion. Unlike some splitting techniques that are limited to linear approximations on rectangular grids, in this work, the solution is approximated by means of piecewise quadratic functions. The main idea of this new reconstructing and limiting technique follows a well‐known approach where local maximum principle regions are defined by enforcing some constraints on the reconstruction of the solution. Numerical comparisons with some existing slope limiters on structured as well as on unstructured meshes show a superior accuracy of our proposed slope limiters. Copyright © 2004 John Wiley & Sons, Ltd.     

A family of lower- and higher-order transversal linearization techniques in non-linear stochastic engineering dynamics

Sample pathwise numerical integration of noise-driven engineering dynamical systems cannot generally be performed beyond a limited level of accuracy, especially when the noise processes are modelled using (filtered) white noises. Recently, a locally transversal linearization (LTL) strategy has been proposed by the author (Proc Roy Soc London A 2001; 457 :539–566) for direct integration of deterministic and stochastic non-linear dynamical systems. The present effort is focussed on a host of extensions along with detailed theoretical error analyses of the linearization approach, especially as applied to problems in non-linear stochastic engineering dynamics. Thus, to begin with, estimates of local and global error orders in the basic LTL scheme are obtained separately for the displacement and velocity vectors when the system is driven either by a set of additive noises or by an arbitrary combination of (independently evolving) additive and multiplicative noises. Following this, a new family of higher-order LTL schemes is proposed in order to improve upon the basic LTL method and the associated error orders are established. A stepwise implementation of the lower- and higher-order versions of the LTL method, along with certain computational aspects, is also outlined. The proposed schemes are numerically illustrated, to a limited extent, for a single degree-of-freedom (SDOF) and a two degree-of-freedom (TDOF) non-linear engineering systems under additive and/or multiplicative white noise excitations. Copyright © 2004 John Wiley & Sons, Ltd.     

A simple approximation algorithm for the weighted matching problem

We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259-269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.     

Implicit–Explicit Schemes for BGK Kinetic Equations

In this work a new class of numerical methods for the BGK model of kinetic equations is presented. In principle, schemes of any order of accuracy in both space and time can be constructed with this technique. The methods proposed are based on an explicit–implicit time discretization. In particular the convective terms are treated explicitly, while the source terms are implicit. In this fashion even problems with infinite stiffness can be integrated with relatively large time steps. The conservation properties of the schemes are investigated. Numerical results are shown for schemes of order 1, 2 and 5 in space, and up to third-order accurate in time.     

Coordinating production and distribution of jobs with bundling operations

We consider an integrated scheduling and distribution model in which jobs completed by two different machines must be bundled together for delivery. The objective is to minimize the sum of the delivery cost and customers' waiting costs. Such a model not only attempts to coordinate the job schedules on both machines, but also aims to coordinate the machine schedules with the delivery plan. Polynomial-time heuristics and approximation schemes are developed for the model with only direct shipments as well as the general model with milk-run deliveries.     

中国的三种非同步轨道卫星移动通信系统星座方案

本文介绍基于我国的三种非同步轨道卫星移动通信系统星座方案：低、中轨系统各有２４和１８颗星，轨道高度分别为１３２６和８０３５ｋｍ，两系统各以５°和３０°的仰角对我国的覆盖率为９９．７８％和９９．９６％；椭圆轨道系统１２颗星，近、远地点分别为４２７和２９０６ｋｍ，以７°和１５°仰角对我国北纬２０°以上地区覆盖率分别为９７．９０％和８９．６１％，若增加４颗中轨卫星，以１５°仰角对我国的覆盖率为９９．９９％。     

Lower bounds on the information rate of secret sharing schemes with homogeneous access structure

We present some new lower bounds on the optimal information rate and on the optimal average information rate of secret sharing schemes with homogeneous access structure. These bounds are found by using some covering constructions and a new parameter, the k-degree of a participant, that is introduced in this paper. Our bounds improve the previous ones in almost all cases.     

Experience with Applying Formal Methods to Protocol Specification and System Architecture

In the last three years or so we at Enterprise Platforms Group at Intel Corporation have been applying formal methods to various problems that arose during the process of defining platform architectures for Intel's processor families. In this paper we give an overview of some of the problems we have worked on, the results we have obtained, and the lessons we have learned. The last topic is addressed mainly from the perspective of platform architects.