Two improved algorithms for envelope and wavefront reduction

Two algorithms for reordering sparse, symmetric matrices or undirected graphs to reduce envelope and wavefront are considered. The first is a combinatorial algorithm introduced by Sloan and further developed by Duff, Reid, and Scott; we describe enhancements to the Sloan algorithm that improve its quality and reduce its run time. Our test problems fall into two classes with differing asymptotic behavior of their envelope parameters as a function of the weights in the Sloan algorithm. We describe an efficientO(nlogn+m) time implementation of the Sloan algorithm, wheren is the number of rows (vertices), andm is the number of nonzeros (edges). On a collection of test problems, the improved Sloan algorithm required, on the average, only twice the time required by the simpler RCM algorithm while improving the mean square wavefront by a factor of three. The second algorithm is a hybrid that combines a spectral algorithm for envelope and wavefront reduction with a refinement step that uses a modified Sloan algorithm. The hybrid algorithm reduces the envelope size and mean square wavefront obtained from the Sloan algorithm at the cost of greater running times. We illustrate how these reductions translate into tangible benefits for frontal Cholesky factorization and incomplete factorization preconditioning. This work was partially supported by the U. S. National Science Foundation grants CCR-9412698, DMS-9505110, and ECS-9527169, by U. S. Department of Energy grant DE-FG05-94ER25216, and by the National Aeronautics and Space Administration under NASA Contract NAS1-19480 while the second author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA.     

The Signaling Problem in Nonlinear Hyperbolic Wave Theory

This work is devoted to investigating weakly nonlinear hyperbolic waves arising from the action of small-amplitude, high-frequency boundary disturbances. By directly introducing a nonlinear phase variable corresponding to the leading wavefront and specifying a single-wave-mode boundary disturbance, we are able to construct an asymptotic solution. Furthermore, our result shows that, by properly arranging the relation of small amplitude to high frequency, a systematic procedure can be provided for constructing weakly nonlinear wave solutions with interior shocks and determining the shock initiation position (and time) when there is a local linear degeneracy at the leading wavefront.     

Traveling wavefronts for a reaction-diffusion-chemotaxis model with volume-filling effect

In this paper, we study the propagation of the pattern for a reaction-diffusionchemotaxis model. By using a weakly nonlinear analysis with multiple temporal and spatial scales, we establish the amplitude equations for the patterns, which show that a local perturbation at the constant steady state is spread over the whole domain in the form of a traveling wavefront. The simulations demonstrate that the amplitude equations capture the evolution of the exact patterns obtained by numerically solving the considered system.     

Time-stepping in Petrov-Galerkin methods based on cubic B-splines for compactons

Four numerical methods with first- to fourth-order of accuracy have been developed for the time integration of the Rosenau-Hyman K(2, 2) equation. The error in the solution and the invariants for the propagation of one-compacton, and the stability in collisions among compactons have been studied using these methods. Numerically-induced radiation has also been characterized by means of wavefront velocity and wavefront amplitude, showing that the self-similarity of the radiation wavepackets observed in the numerical results is a consequence of the time-stepping method. Among the four methods studied in this paper, the best results in terms of accuracy, computational cost, and stability have been obtained by means of using the second-order time integration method.     

Cross-Diffusion Driven Instability in a Predator-Prey System with Cross-Diffusion

In this work we investigate the process of pattern formation induced by nonlinear diffusion in a reaction-diffusion system with Lotka-Volterra predator-prey kinetics. We show that the cross-diffusion term is responsible of the destabilizing mechanism that leads to the emergence of spatial patterns. Near marginal stability we perform a weakly nonlinear analysis to predict the amplitude and the form of the pattern, deriving the Stuart-Landau amplitude equations. Moreover, in a large portion of the subcritical zone, numerical simulations show the emergence of oscillating patterns, which cannot be predicted by the weakly nonlinear analysis. Finally, when the pattern invades the domain as a travelling wavefront, we derive the Ginzburg-Landau amplitude equation which is able to describe the shape and the speed of the wave.     

The most-energetic traveltime of seismic waves

In tomographic image processing of seismic data, the first-arrival traveltime (FATT) is often different from those of more energetic wavefronts in realistic media. Since the traveltime of most-energetic wavefront (METT) dominates the data, computing the METT is recognized as an essential element in modern seismic imaging techniques. Solving the full wave equation is extremely expensive to be impractical even for large-size computers to carry out; the solution of the eikonal equation for which the corresponding amplitude is continuous is conjectured to be the METT.     

Wavefront cache-friendly algorithm for compact numerical schemes

Compact numerical schemes provide high-order solution of PDEs with low dissipation and dispersion. Computer implementation of these schemes requires numerous passes of data through cache memory that considerably reduces performance of these schemes. To reduce this difficulty, a novel algorithm is proposed here. This algorithm is based on a wavefront approach and sweeps through cache memory only twice.     

A light-propagation model for aircraft trajectory planning

Predicted air traffic growth is expected to double the number of flights over the next 20 years. If current means of air traffic control are maintained, airspace capacity will reach its limits. The need for increasing airspace capacity motivates improved aircraft trajectory planning in 4D (space+time). In order to generate sets of conflict-free 4D trajectories, we introduce a new nature-inspired algorithm: the light propagation algorithm (LPA). This algorithm is a wavefront propagation method that yields approximate geodesic solutions (minimal-in-time solutions) for the path planning problem, in the particular case of air-traffic congestion. In simulations, LPA yields encouraging results on real-world traffic over France while satisfying the specific constraints in air-traffic management.     

Asymptotic speed of propagation and traveling wavefronts in a non-local delayed lattice differential equation

In this paper, we study a very general non-local lattice differential equation with delay. We obtain the existence of the asymptotic speed of propagation, the existence and uniqueness of the traveling wavefront and the minimal speed of the traveling wavefront for the system. We also confirm that the asymptotic speed of propagation and the minimal speed of the traveling wavefront coincide.     

Adiabatic Vacuum States on General Spacetime Manifolds: Definition, Construction, and Physical Properties

Adiabatic vacuum states are a well-known class of physical states for linear quantum fields on Robertson-Walker spacetimes. We extend the definition of adiabatic vacua to general spacetime manifolds by using the notion of the Sobolev wavefront set. This definition is also applicable to interacting field theories. Hadamard states form a special subclass of the adiabatic vacua. We analyze physical properties of adiabatic vacuum representations of the Klein-Gordon field on globally hyperbolic spacetime manifolds (factoriality, quasiequivalence, local definiteness, Haag duality) and construct them explicitly, if the manifold has a compact Cauchy surface.     

Reconstruction of a Source from Observational Data

A procedure is described for determining the strength, position, and startup time of a surface force source acting on an elastic half-space from recorded data on the vertical displacements (seismograms) of a linear oscillator (seismograph). The algorithm is based on a previously published analytical solution of the Lamb problem. Special attention is given to the role of the Rayleigh wavefront as a generator of displacements much larger than in the approach of P waves and SV waves to the seismograph, revealing the Rayleigh wave as the primary indicator of a source's space–time position.     

Evolution of weak discontinuities in a non-ideal radiating gas

A method of wavefront analysis is used to study the formation of shock waves in a two-dimensional steady supersonic flow of a non-ideal radiating gas past plane and axisymmetric bodies. The gas is taken to be sufficiently hot for the effect of thermal radiation to be significant, which is, of course, treated by the optically thin approximation to the radiative transfer equation. Transport equations, which lead to the determination of the shock formation distance and also to conditions which insure that no shock will ever evolve on the wavefront, is derived. The influence of the parameter of the non-idealness, upstream flow Mach number in the presence of thermal radiation on the behavior of the wavefront are examined.     

Numerical solution of RLW equation using linear finite elements within Galerkin's method

The regularised long wave equation is solved by Galerkin's method using linear space finite elements. In the simulations of the migration of a single solitary wave, this algorithm is shown to have good accuracy for small amplitude waves. Moreover, for very small amplitude waves (⩽0.09) it has higher accuracy than an approach using quadratic B-spline finite elements within Galerkin's method. The interaction of two solitary waves is modelled for small amplitude waves.     

Formation of wavy nanostructures on the surface of flat substrates by ion bombardment

A popular mathematical model for the formation of an inhomogeneous topography on the surface of a plate (flat substrate) during ion bombardment was considered. The model is described by the Bradley-Harper equation, which is frequently referred to as the generalized Kuramoto-Sivashinsky equation. It was shown that inhomogeneous topography (nanostructures in the modern terminology) can arise when the stability of the plane incident wavefront changes. The problem was solved using the theory of dynamical systems with an infinite-dimensional phase space, in conjunction with the integral manifold method and Poincaré-Dulac normal forms. A normal form was constructed using a modified Krylov-Bogolyubov algorithm that applies to nonlinear evolutionary boundary value problems. As a result, asymptotic formulas for solutions of the given nonlinear boundary value problem were derived.     

Quickest Paths, Straight Skeletons, and the City Voronoi Diagram

The city Voronoi diagram is induced by quickest paths in the L ₁plane, made faster by an isothetic transportation network. We investigate the rich geometric and algorithmic properties of city Voronoi diagrams, and report on their use in processing quickest-path queries. In doing so, we revisit the fact that not every Voronoi-type diagram has interpretations in both the distance model and the wavefront model. Especially, straight skeletons are a relevant example where an interpretation in the former model is lacking. We clarify the relationship between these models, and further draw a connection to the bisector-defined abstract Voronoi diagram model, with the particular goal of computing the city Voronoi diagram efficiently.     

Recovering wavefronts from difference measurements in lateral shearing interferometry

Results of lateral shearing interferograms are difference measurements of a wavefront under study, from which this wavefront is to be reconstructed. Properties of the difference operator associated with a shearing experiment are discussed. It is shown that the Moore–Penrose generalized inverse is bounded and it is given in an explicit form for suitably chosen shearing parameters.     

Bistable wavefronts in a diffusive and competitive Lotka-Volterra type system with nonlocal delays

A diffusive Lotka-Volterra type model with nonlocal delays for two competitive species is considered. The existence of a traveling wavefront analogous to a bistable wavefront for a single species is proved by transforming the system with nonlocal delays to a four-dimensional system without delay. Furthermore, in order to prove the asymptotic stability (up to translation) of bistable wavefronts of the system, the existence, regularity and comparison theorem of solutions of the corresponding Cauchy problem are first established for the systems on R by appealing to the theory of abstract functional differential equations. The asymptotic stability (up to translation) of bistable wavefronts are then proved by spectral methods. In particular, we also prove that the spreading speed is unique by upper and lower solutions technique. From the point of view of ecology, our results indicate that the nonlocal delays appeared in the interaction terms are not sensitive to the invasion of species of spatial isolation.     

On finite amplitude spherical acceleration waves in homogeneously deformed hyperelastic materials

Summary By employing the wavefront analysis of Jeffrey [2], the growth and decay of finite amplitude spherical acceleration waves in an initially deformed isotropic hyperelastic materials is investigated. The results are specialized for Ko material and compared with those obtained via the method of propagating singular surfaces. The effect of initial deformation on acceleration waves is also discussed for this special material.

---

Zusammenfassung Durch Anwendung der Wellenfrontanalyse von Jeffrey [2], wurden der Zuwachs und die Dämpfung der sphärischen Beschleunigungswellen mit endlichen Amplituden in einem deformierten, isotropischen, hyperelastischen Material untersucht. Die Ergebnisse wurden für das Ko Material spezialisiert und verglichen mit denjenigen, die durch die Methode der fortschreitenden singulären Flächen gewonnen wurden. Für dieses besondere Material wurde auch der Einfluß der Anfangsdeformationen an die Beschleunigungswellen diskutiert.

     

Kawaguchi space,Zermelo's condition and seismic ray path

Based on Kawaguchi space, a seismic ray path through an anisotropic medium corresponds to an arclength under Zermelo's condition. From a special function in Kawaguchi space, we obtain some Finslerian metrics (mth root metric or 1-form metric). Considering a variational problem of the seismic ray, Snell's law is derived from Euler's vector, and envelopes of seismic wavefront are classified by m-values in seismic Finsler metric. Moreover, we discuss the relation between Kawaguchi space and another ray theory.     

Reconstruction of random-disturbance amplitude in linear stochastic equations from measurements of some of the coordinates

The problem of reconstructing the unknown amplitude of a random disturbance in a linear stochastic differential equation is studied in a fairly general formulation by applying dynamic inversion theory. The amplitude is reconstructed using discrete information on several realizations of some of the coordinates of the stochastic process. The problem is reduced to an inverse one for a system of ordinary differential equations satisfied by the elements of the covariance matrix of the original process. Constructive solvability conditions in the form of relations on the parameters of the system are discussed. A finite-step software implementable solving algorithm based on the method of auxiliary controlled models is tested using a numerical example. The accuracy of the algorithm is estimated with respect to the number of measured realizations.