Multi-resolution analysis on the interval with natural spline projection and uniform two-scale relation

The aim of this paper is to present a modification to the Chui and Quak (1992) spline multiresolution analysis for the finite interval. Boundary scaling functions with multipole nodes at interval endpoints are rejected, in favor of the classical B-spline scaling function restricted to the interval. This necessitates derivation of revised boundary wavelets. In addition, a direct method of decomposition results in bandwidth reduction on solving some associated linear systems, and image distortion is reduced by employing natural spline projection. Finally, a hybrid projection scheme is proposed, which particularly for large systems further lowers operation count. Numerical experiments proving the algorithm are indicated.     

Optimal decompositions of matrices with grades into binary and graded matrices

We study the problem of decomposition of object-attribute matrices whose entries contain degrees to which objects have attributes. The degrees are taken from a bounded partially ordered scale. Examples of such matrices are binary matrices, matrices with entries from a finite chain, or matrices with entries from the unit interval [0, 1]. We study the problem of decomposition of a given object-attribute matrix I with degrees into an object-factor matrix A with degrees and a binary factor-attribute matrix B, with the number of factors as small as possible. We present a theorem which shows that decompositions which use particular formal concepts of I as factors for the decomposition are optimal in that the number of factors involved is the smallest possible. We show that the problem of computing an optimal decomposition is NP-hard and present two heuristic algorithms for its solution along with their experimental evaluation. For the first algorithm, we provide its approximation ratio. Experiments indicate that the second algorithm, which is considerably faster than the first one, delivers decompositions whose quality is comparable to the decompositions delivered by the first algorithm. We also present an illustrative example demonstrating a factor analysis interpretation of the decomposition studied in this paper.     

Solution of the Schrödinger equation over an infinite integration interval by perturbation methods, revisited

We consider the solution of the one-dimensional Schrödinger problem over an infinite integration interval. The infinite problem is regularized by truncating the integration interval and imposing the appropriate boundary conditions at the truncation points. The Schrödinger problem is then solved on the truncated integration interval using one of the piecewise perturbation methods developed for the regular Schrödinger problem.We select the truncation points using a procedure based on the WKB approximation. However for problems which behave as a Coulomb problem both around the origin and in the asymptotic range, a more accurate treatment of the numerical boundaries is possible. Taking into account the asymptotic form of the Coulomb equation, adapted boundary conditions can be constructed and as a consequence smaller truncation points can be chosen. To deal with the singularity of the Coulomb-like problem around the origin, a special perturbative algorithm is applied in a small interval around the origin.     

Asymptotic boundary conditions with immersed finite elements for interface magnetostatic/electrostatic field problems with open boundary

Many of the magnetostatic/electrostatic field problems encountered in aerospace engineering, such as plasma sheath simulation and ion neutralization process in space, are not confined to finite domain and non-interface problems, but characterized as open boundary and interface problems. Asymptotic boundary conditions (ABC) and immersed finite elements (IFE) are relatively new tools to handle open boundaries and interface problems respectively. Compared with the traditional truncation approach, asymptotic boundary conditions need a much smaller domain to achieve the same accuracy. When regular finite element methods are applied to an interface problem, it is necessary to use a body-fitting mesh in order to obtain the optimal convergence rate. However, immersed finite elements possess the same optimal convergence rate on a Cartesian mesh, which is critical to many applications. This paper applies immersed finite element methods and asymptotic boundary conditions to solve an interface problem arising from electric field simulation in composite materials with open boundary. Numerical examples are provided to demonstrate the high global accuracy of the IFE method with ABC based on Cartesian meshes, especially around both interface and boundary. This algorithm uses a much smaller domain than the truncation approach in order to achieve the same accuracy.     

Mesoscopic simulations of electroosmotic flow and electrophoresis in nanochannels

We review recent dissipative particle dynamics (DPD) simulations of electrolyte flow in nanochannels. A method is presented by which the slip length δB at the channel boundaries can be tuned systematically from negative to infinity by introducing suitably adjusted wall-fluid friction forces. Using this method, we study electroosmotic flow (EOF) in nanochannels for varying surface slip conditions and fluids of different ionic strength. Analytic expressions for the flow profiles are derived from the Stokes equation, which are in good agreement with the numerical results. Finally, we investigate the influence of EOF on the effective mobility of polyelectrolytes in nanochannels. The relevant quantity characterizing the effect of slippage is found to be the dimensionless quantity κδB, where 1/κ is an effective electrostatic screening length at the channel boundaries.     

An improved truncation technique to analyze a Geo/PH/1 retrial queue with impatient customers

This paper considers a discrete-time retrial queue with impatient customers. We establish the global balance equations of the Markov chain describing the system evolution and prove that this queueing system is stable as long as the customers are strict impatient and the mean retrial time is finite. Direct truncation with matrix decomposition is used to approximate the steady-state distribution of the system state and hence derive a set of performance measures. The proposed matrix decomposition scheme is presented in a general form which is applicable to any finite Markov chain of the GI/M/1-type. It represents a generalization of the Gaver–Jacobs–Latouche's algorithm that deals with QBD process. Different sets of numerical results are presented to test the efficiency of this technique compared to the generalized truncation one. Moreover, an emphasis is put on the effect of impatience on the main performance measures.     

Quantum Mereotopology

While mereotopology – the theory of boundaries, contact and separation built up on a mereological foundation – has found fruitful applications in the realm of qualitative spatial reasoning, it faces problems when its methods are extended to deal with those varieties of spatial and non-spatial reasoning which involve a factor of granularity. This is because granularity cannot easily be represented within a mereology-based framework. We sketch how this problem can be solved by means of a theory of granular partitions, a theory general enough to comprehend not only the familiar sorts of spatial partitions but also a range of coarse-grained partitions of other, non-spatial sorts. We then show how these same methods can be extended to apply to finite sequences of granular partitions evolving over time, or to what we shall call coarse- and fine-grained histories.     

Analysis of a class of communicating finite state machines

Thereachability, deadlok detection andunboundedness detection problems are considered for the class ofcyclic one-type message networks of communicating finite state machines. We show that all the three problems are effectively solvable by (a) constructing canonical execution event sequences which belong to a context-free language, and (b) showing that the reachability sets are semilinear. Our algorithms have polynomial complexity in terms of size of a global structure of a network, called theshuffle-product. The relationships between general Petri nets and the class of communicating finite state machines considered here are also explored.Supported in part by NSF CCR-9004121     

Transformation of a continuous time-invariant linear system into a discrete one

A discrete-time time-invariant linear system (DILS) is considered which has resulted from the discretization of a continuous-time time-invariant linear system (CILS) by the zero order hold. In this system, the system and input matrices are given by exp(AT) and $ where A and B are the system and input matrices of the CILS, and T is a sampling interval. Since they involve the matrix exponential, their computations are not easy.

First, on the assumption that the Kalman canonical form of the CILS is sought, a formal Kalman canonical form of the DILS is determined. Second, with the use of this form and the decomposition of A into the projectors onto the generalized eigenspaces, an algorithm is presented which computes the system and input matrices of the DlLS.     

A new procedure for evaluating the time domain boundary influence matrix of unbounded media

The finite element method can only deal with finite domains with well defined boundaries. For dynamic problems involving unbounded media, the boundaries of the finite model distort the real physical behaviour of the problem if they remain untreated. For many problems it is possible to formulate so-called silent boundary conditions which perfectly simulate the effect of the truncated unbounded medium. Unfortunately, most of these conditions are properly formulated in the frequency domain.

The present paper introduces a new procedure which employs these frequency-dependent boundary conditions to calculate the time domain influence matrix of the truncated unbounded medium. This matrix, which was introduced in a previous publication, is used to calculate the reflection-free response of the truncation boundary one time step ahead of the present time station. The known boundary response is then used as a prescribed condition for the finite model. A one-dimensional example with a frequency-dependent boundary condition is presented to examine the effectiveness of the new procedure. Two other silent boundary conditions formulated directly in the time domain are also examined.     

The complementary-slackness class of hybrid systems

In this paper we understand a “hybrid system” to be one that combines features of continuous dynamical systems with characteristics of finite automata. We study a special class of such systems which we call the complementary-slackness class. We study existence and uniqueness of solutions in the special'cases oflinear andHamiltonian complementary-slackness systems. For the latter class we also prove an energy inequality.     

A New Smoothness Indicator for the WENO Schemes and Its Effect on the Convergence to Steady State Solutions

The convergence to steady state solutions of the Euler equations for the fifth-order weighted essentially non-oscillatory (WENO) finite difference scheme with the Lax–Friedrichs flux splitting [7, (1996) J. Comput. Phys. 126, 202–228.] is studied through systematic numerical tests. Numerical evidence indicates that this type of WENO scheme suffers from slight post-shock oscillations. Even though these oscillations are small in magnitude and do not affect the “essentially non-oscillatory” property of WENO schemes, they are indeed responsible for the numerical residue to hang at the truncation error level of the scheme instead of settling down to machine zero. We propose a new smoothness indicator for the WENO schemes in steady state calculations, which performs better near the steady shock region than the original smoothness indicator in [7, (1996) J. Comput. Phys. 126, 202–228.]. With our new smoothness indicator, the slight post-shock oscillations are either removed or significantly reduced and convergence is improved significantly. Numerical experiments show that the residue for the WENO scheme with this new smoothness indicator can converge to machine zero for one and two dimensional (2D) steady problems with strong shock waves when there are no shocks passing through the domain boundaries. Dedicated to the memory of Professor Xu-Dong Liu.     

Scanning Multiple Sequences via Cache Memory

Abstract. We consider the simple problem of scanning multiple sequences. There are k sequences of total length N which are to be scanned concurrently. One pointer into each sequence is maintained and an adversary specifies which pointer is to be advanced. The concept of scanning multiple sequence is ubiquitous in algorithms designed for hierarchical memory. In the external memory model of computation with block size B , a memory consisting of m blocks, and at most m sequences the problem is trivially solved with N/B memory misses by reserving one block of memory for each sequence. However, in a cache memory with associativity a , every access may lead to a cache fault if k > a . For a direct mapped cache (a = 1 ) two sequences suffice. We show that by randomizing the starting addresses of the sequences the number of cache misses can be kept to O(N/B) provided that k = O(m/B ^1/a ) , i.e., the number of sequences that can be supported is decreased by a factor B ^1/a . We also show a corresponding lower bound. Our result leads to a general method for converting sequence based algorithms designed for the external memory model of computation to cache memory even for caches with small associativity.     

Domain decomposition algorithm based on the group explicit formula for the heat equation

A finite difference domain decomposition algorithm (DDA) for solving the heat equation in parallel is presented. In this procedure, interface values between subdomains are calculated by the group explicit formula, whereas interior values of subdomains are determined by the classical implicit scheme. The stability and convergence for this DDA are proved. The stability bound of the procedure is derived to be eight times that of the classical explicit scheme. Though the truncation error at the interface is O(τ?+?h), L ²-error is proved to be O(τ?+?h ²). Numerical examples confirm the second-order convergence and indicate that the stability condition is sharp. A comparison of the numerical errors of this procedure with other known methods is also included.     

An Efficient Discretization of the Navier–Stokes Equations in an Axisymmetric Domain. Part 1: The Discrete Problem and its Numerical Analysis

Any solution of the Navier–Stokes equations in a three-dimensional axisymmetric domain admits a Fourier expansion with respect to the angular variable, and it can be noted that each Fourier coefficient satisfies a variational problem on the meridian domain, all problems being coupled due to the nonlinear convection term. We propose a discretization of these equations which combines Fourier truncation and finite element methods applied to each two-dimensional system. We perform the a priori and a posteriori analysis of this discretization.     

A binary operation on trees and an initial algebra characterization for finite tree types

Summary A binary operation on the class of trees is defined that generates a set B of finite trees form a trivial tree (one node) and B contains for every finite tree G exactly one element isomorphic to G. The binary operation defines an algebraic structure on B, and as a consequence the finite tree types are characterized as an initial algebra in the same way as the natural numbers are characterized as an initial algebra by the Peano-Lawvere axiom [2]. Simple and primitive recursion are defined and some applications of the initial algebra characterization are given.     

Parallel adaptive mesh generation and decomposition

An important class of methodologies for the parallel processing of computational models defined on some discrete geometric data structures (i.e. meshes, grids) is the so calledgeometry decomposition or splitting approach. Compared to the sequential processing of such models, the geometry splitting parallel methodology requires an additional computational phase. It consists of the decomposition of the associated geometric data structure into a number of balancedsubdomains that satisfy a number of conditions that ensure the load balancing and minimum communication requirement of the underlying computations on a parallel hardware platform. It is well known that the implementation of the mesh decomposition phase requires the solution of a computationally intensive problem. For this reason several fast heuristics have been proposed. In this paper we explore a decomposition approach which is part of a parallel adaptive finite element mesh procedure. The proposed integrated approach consists of five steps. It starts with a coarse background mesh that isoptimally decomposed by applying well known heuristics. Then, the initial mesh is refined in each subdomain after linking the new boundaries introduced by its decomposition. Finally, the decomposition of the new refined mesh is improved so that it satisfies the objectives and conditions of the mesh decomposition problem. Extensive experimentation indicates the effectiveness and efficiency of the proposed parallel mesh and decomposition approach.     

The Determination of Stability Boundaries and Control Energy for a Finite Pulse Width Sampled-Data System†

Stability inequalities relating five system parameters have been derived using state apace analysis for n finite pulse sampled-data system. Further, these inequalities have been utilized to compute absolute stability boundaries in n parameter space and in particular their variation with pulse width and sampling period is described.

An expression for the control energy as a function of the state variables has been derived and computer results are presented which show the variation of the asymptotic value of control energy per interval with pulse width. It is further shown how points of inflection in the control energy per interval pulse width curve, may be utilized to minimize the sensitivity of control energy per interval to pulse width timing errors.     

I/O-Efficient Algorithms for Graphs of Bounded Treewidth

We present an algorithm that takes I/Os (sort(N)=Θ((N/(DB))log  _M/B (N/B)) is the number of I/Os it takes to sort N data items) to compute a tree decomposition of width at most k, for any graph G of treewidth at most k and size N, where k is a constant. Given such a tree decomposition, we use a dynamic programming framework to solve a wide variety of problems on G in I/Os, including the single-source shortest path problem and a number of problems that are NP-hard on general graphs. The tree decomposition can also be used to obtain an optimal separator decomposition of G. We use such a decomposition to perform depth-first search in G in  I/Os. As important tools that are used in the tree decomposition algorithm, we introduce flippable DAGs and present an algorithm that computes a perfect elimination ordering of a k-tree in I/Os. The second contribution of our paper, which is of independent interest, is a general and simple framework for obtaining I/O-efficient algorithms for a number of graph problems that can be solved using greedy algorithms in internal memory. We apply this framework in order to obtain an improved algorithm for finding a maximal matching and the first deterministic I/O-efficient algorithm for finding a maximal independent set of an arbitrary graph. Both algorithms take I/Os. The maximal matching algorithm is used in the tree decomposition algorithm. An abstract of this paper was presented at the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pp. 89–90, 2001. Research of A. Maheshwari supported by NSERC. Part of this work was done while the second author was a Ph.D. student at the School of Computer Science of Carleton University.