A note on the accuracy of spectral method applied to nonlinear conservation laws

Fourier spectral method can achieve exponential accuracy both on the approximation level and for solving partial differential equations if the solutions are analytic. For a linear PDE with discontinuous solutions, Fourier spectral method will produce poor point-wise accuracy without post-processing, but still maintains exponential accuracy for all moments against analytic functions. In this note we assess the accuracy of Fourier spectral method applied to nonlinear conservation laws through a numerical case study. We have found out that the moments against analytic functions are no longer very accurate. However the numerical solution does contain accurate information which can be extracted by a Gegenbauer polynomial based post-processing.Research supported by ARO Grant DAAL03-91-G-0123 and DAAH04-94-G-0205, NSF Grant DMS-9211820, NASA Grant NAG1-1145 and contract NAS1-19480 while the first author was in residence at ICASE, NASA Langley Research Center, Hampton, Virginia 23681-0001, and AFOSR Grant 93-0090.     

Implementation of a parallel unstructured Euler solver on shared- and distributed-memory architectures

An efficient three-dimensional unstructured Euler solver is parallelized on a CRAY Y-MP C90 shared-memory computer and on an Intel Touchstone Delta distributed-memory computer. This paper relates the experiences gained and describes the software tools and hardware used in this study. Performance comparisons between the two differing architectures are made.This work was sponsored in part by ARPA (NAG-1-1485) and by NASA Contract No. NAS1-19480 while authors Mavriplis, Saltz and Das were in residence at ICASE, NASA Langley Research Center, Hampton, Virginia. This research was performed in part using the Intel Touchstone Delta System operated by Caltech on behalf of the Concurrent Supercomputing Consortium. Access to this fecility was provided by NASA Langley Research Center and the Center for Research in Parallel Processing. The content of the information does not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred.     

Wave envelope technique for multimode wave guide problems

In this paper we propose a fast method for solving wave guide problems. In particular, we consider the guide to be inhomogeneous, and allow propagation of waves of higher-order modes. Such techniques have been handled successfully for acoustic wave propagation problems with single mode and finite length. This paper extends this concept to electromagnetic wave guides with several modes and infinite in length. The method is shown and results of computations are presented.Research was supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-18107 while the first author was in residence at the ICASE, NASA Langley Research Center, Hampton, VA 23665-5225, and by NASA Grant No. NAG-1-624.     

Delay point schedules for irregular parallel computations

In irregular scientific computational problems one is periodically forced to choosea delay point where some overhead cost is suffered to ensure correctness, or to improve subsequent performance. Examples of delay points are problem remappings, and global synchronizations. One sometimes has considerable latitude in choosing the placement and frequency of delay points; we consider the problem of scheduling delay points so as to minimize the overal execution time. We illustrate the problem with two examples, a regridding method which changes the problem discretization during the course of the computation, and a method for solving sparse triangular systems of linear equations. We show that one can optimally choose delay points in polynomial time using dynamic programming. However, the cost models underlying this approach are often unknown. We consequently examine a scheduling heuristic based on maximizing performance locally, and empirically show it to be nearly optimal on both problems. We explain this phenomenon analytically by identifying underlying assumptions which imply that overall performance is maximized asymptotically if local performance is maximized.This research was supported in part by the National Aeronautics and Space Administration under NASA contract NAS1-18107 while the author consulted at ICASE, Mail Stop 132C, NASA Langley Research Center, Hampton, Virginia 23665.Supported in part by NASA contract NAS1-18107, the Office of Naval Research under Contract No. N00014-86-K-0654, and NSF Grant DCR 8106181.     

Semi-automatic process partitioning for parallel computation

Automatic process partitioning is the operation of automatically rewriting an algorithm as a collection of tasks, each operating primarily on its own portion of the data, to carry out the computation in parallel. Hybrid shared memory systems provide a hierarchy of globally accessible memories. To achieve high performance on such machines one must carefully distribute the work and the data so as to keep the workload balanced while optimizing the access to nonlocal data. In this paper we consider a semi-automatic approach to process partitioning in which the compiler, guided by advice from the user, automatically transforms programs into such an interacting set of tasks. This approach is illustrated with a picture processing example written in BLAZE, which is transformed by the compiler into a task system maximizing locality of memory reference.Research supported by an IBM Graduate Fellowship.Research supported under NASA Contract No. 520-1398-0356.Research supported by NASA Contract No. NAS1-18107 while the last two authors were in residence at ICASE, NASA, Langley Research Center.     

Numerical experiments on the accuracy of ENO and modified ENO schemes

In this paper we make further numerical experiments assessing an accuracy degeneracy phenomena reported by A. Rogerson and E. Meiburg (this issue, 1990). We also propose a modified ENO scheme, which recovers the correct order of accuracy for all the test problems with smooth initial conditions and gives results comparable to the original ENO schemes for discontinuous problems.Research supported by NSF grant No. DMS88-10150, NASA Langley contract No. NAS1-18605, and AFOSR grant No. 90-0093. Computation supported by NAS.     

Rational trigonometric approximations using Fourier series partial sums

A class of approximations {S _N,M } to a periodic functionf which uses the ideas of Padé, or rational function, approximations based on the Fourier series representation off, rather than on the Taylor series representation off, is introduced and studied. Each approximationS _N,M is the quotient of a trigonometric polynomial of degreeN and a trigonometric polynomial of degreeM. The coefficients in these polynomials are determined by requiring that an appropriate number of the Fourier coefficients ofS _N,M agree with those off. Explicit expressions are derived for these coefficients in terms of the Fourier coefficients off. It is proven that these Fourier-Padé approximations converge point-wise to (f(x ⁺) +f(x ^–))/2 more rapidly (in some cases by a factor of 1/k ^2M ) than the Fourier series partial sums on which they are based. The approximations are illustrated by several examples and an application to the solution of an initial, boundary value problem for the simple heat equation is presented.This research was supported by NASA contract NAS1-19480 while the author was in residence at ICASE, NASA Langley Research Center, Hampton, Virginia 23665.     

Approximate algorithms for partitioning problems

We consider the problem of optimally assigning the modules of a parallel/pipelined program over the processors of a multiple processor system under certain restrictions on the interconnection structure of the program as well as the multiple computer system. We show that for a variety of such problems, it is possible to find if a partition of the modular program exists in which the load on any processor is whithin a certain bound. This method when combined with a binary search over a fixed range, provides an optimal solution to the partitioning problem.The specific problems we consider are partitioning of (1) a chain structured parallel program over a chain-like computer system, (2) multiple chain-like programs over a host-satellite system, and (3) a tree structured parallel program over a host-satellite system.For a problem withN modules andM processors, the complexity of our algorithm is no worse thanO(Mlog(N)log(W _T/)), whereW _T is the cost of assigning all modules to one processors, and the desired accuracy. This algorithm provides an improvement over the recently developed best known algorithm that runs inO(MNlog(N)) time.This Research was supported by a grant from the Division of Research Extension and Advisory Services, University of Engineering and Technology Lahore, Pakistan. Further support was provided by NASA Contracts NAS1-17070 and NAS1-18107 while the author was resident at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, Virginia, USA.     

Comparison of methods for developing dynamic reduced models for design optimization

In this paper we compare three methods for forming reduced models to speed up genetic-algorithm-based optimization. The methods work by forming functional approximations of the fitness function which are used to speed up the GA optimization by making the genetic operators more informed. Empirical results in several engineering design domains are presented.This research was funded in part by a sub-contract from the Rutgers-based Self Adaptive Software project supported by the Advanced Research Projects Agency of the Department of Defense and by NASA under grant NAG2-1234.     

High-order centered difference methods with sharp shock resolution

High-order centered finite difference approximations of hyperbolic conservation laws are considered. Different ways of adding artificial viscosity to obtain sharp shock resolution are proposed. For the Riemann problem simple explicit formulas for obtaining stationary one- and two-point shocks are presented. This can be done for any order of accuracy. It is shown that the addition of artificial viscosity is equivalent to ensuring the Laxk-shock condition. Numerical experiments verify the theoretical results.This work has been sponsored by NASA under Contract No. NAS 2-13721.     

Observability for two-dimensional systems

Sufficient conditions that a two-dimensional system with output is locally observable are presented. Known results depend on time derivatives of the output and the inverse function theorem. In some cases, no information is provided by these theories, and one must study observability by other methods. We dualize the observability problem to the controllability problem, and apply the deep results of Hermes on local controllability to prove a theorem concerning local observability.Research supported by NASA Ames Research Center under Grant NAG2-189 and the Joint Services Electronics Program under ONR Contract N0014-76-C1136.Research supported by NASA Ames Research Center under Grant NAG2-203 and the Joint Services Electronics Program under ONR Contract N0014-76-C1136.     

Analysis of an identification algorithm arising in the adaptive estimation of Markov chains

We investigate an algorithm applied to the adaptive estimation of partially observed finite-state Markov chains. The algorithm utilizes the recursive equation characterizing the conditional distribution of the state of the Markov chain, given the past observations. We show that the process “driving” the algorithm has a unique invariant measure for each fixed value of the parameter, and following the ordinary differential equation method for stochastic approximations, establish almost sure convergence of the parameter estimates to the solutions of an associated differential equation. The performance of the adaptive estimation scheme is analyzed by examining the induced controlled Markov process with respect to a long-run average cost criterion. This research was supported in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860 and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.     

A framework for protein structure prediction on the grid

The large number of protein sequences, provided by genomic projects at an increasing pace, constitutes a challenge for large scale computational studies of protein structure and thermodynamics. Grid technology is very suitable to face this challenge, since it provides a way to access the resources needed in compute and data intensive applications. In this paper, we show the procedure to adapt to the Grid an algorithm for the prediction of protein thermodynamics, using the GridWay tool. GridWay allows the resolution of large computational experiments by reacting to events dynamically generated by both the Grid and the application. Eduardo Huedo, Ph.D.: He is a Computer Engineer (1999) and Ph.D. in Computer Architecture (2004) by the Universidad Complutense de Madrid (UCM). He is Scientist in the Advanced Computing Laboratory at Centro de Astrobiología (CSIC-INTA), associated to NASA Astrobiology Institute. He had one appointment in 2000 as a Summer Student in High Performance Computing and Applied Mathematics at ICASE (NASA Langley Research Center). His research areas are Performance Management and Tuning, High Performance Computing and Grid Technology. Ugo Bastolla, Ph.D.: He received his degree and Ph.D. in Physics in Rome University, with L. Peliti and G. Parisi respectively. He was interested from the beginning in biologically motivated problems, therefore, studied models of Population Genetics, Boolean Networks, Neural Networks, Statistical Mechanics of Polymers, Ecological and Biodiversity. His main research interest is constituted by studies of protein folding thermodynamics and evolution. Thereby, he set up an effective energy function allowing prediction of protein folding thermodynamics, and applied it to protein structure prediction, to simulate protein evolution and to analyze protein sequences from a thermodynamical point of view. He is currently in the Bioinformatic Unit of the Centro de Astrobiología of Madrid. Rubén S. Montero, Ph.D.: He received his B.S. in Physics (1996), M.S in Computer Science (1998) and Ph.D. in Computer Architecture (2002) from the Universidad Complutense de Madrid (UCM). He is Assistant Professor of Computer Architecture and Technology at UCM since 1999. He has held several research appointments at ICASE (NASA Langley Research Center), where he worked on computational fluid dynamics, parallel multigrid algorithms and Cluster computing. Nowadays, his research interests lie mainly in Grid Technology, in particular in adaptive scheduling, adaptive execution and distributed algorithms. Ignacio M. Llorente, Ph.D.: He received his B.S. in Physics (1990), M.S in Computer Science (1992) and Ph.D. in Computer Architecture (1995) from the Universidad Complutense de Madrid (UCM). He is Executive M.B.A. by Instituto de Empresa since 2003. He is Associate Professor of Computer Architecture and Technology in the Department of Computer Architecture and System Engineering at UCM and Senior Scientist at Centro de Astrobiología (CSIC-INTA), associated to NASA Astrobiology Institute. He has held several appointments since 1997 as a Consultant in High Performance Computing and Applied Mathematics at ICASE (NASA Langley Research Center). His research areas are Information Security, High Performance Computing and Grid Technology.     

On optimizing the evaluation of a set of expressions

A branch- and-bound type algorithm is developed to optimize the evaluation of a set of expressions. The algorithm proceeds in a depth-first manner and achieves an optimal solution. The algorithm is applied to optimize the evaluation of sets of relational expressions. Analogies to the heuristic information associated with theA* algorithm are investigated. Examples are presented illustrating the use of the algorithm. Pragmatics associated with the algorithm and its application to Boolean optimization are also discussed.Research supported by the National Science Foundation under grant number NSF MCS 79-19418 and by the National Aeronautics and Space Administration under grant number NGR 21-002-270-9.     

Degradation reduction in optics imagery using Toeplitz structure

This paper is concerned with improvement in optical image quality by image restoration. Image restoration is an ill-posed inverse problem which involves the removal or minimization of degradations caused by noise and blur in an image, resulting from, in this case, imaging through a medium. Our work here concerns the use of the underlying Toeplitz structure of such problems, and associated techniques for accelerating the convergence of iterative image restoration computations. Denoising methods, including total variation minimization, followed by segmentation-based preconditioning methods for minimum residual conjugate gradient iterations, are investigated. Regularization is accomplished by segmenting the image into (smooth) segments and varying the preconditioners across the segments. By taking advantage of the Toeplitz structure, our algorithms can be implemented with computational complexity of onlyO (ln ² logn), wheren ² is the number of pixels in the image andl is the number of segments used. Also, parallelization is straightforward. Numerical tests are reported for atmospheric imaging problems, including the case of spatially varying blur. Research supported in part by a National Science Foundation Postdoctoral Research Fellowship. Research sponsored by the U.S. Air Force Office of Scientific Research under grant F49620-97-1-1039. Research sponsored by the U.S. Air Force Office of Scientific Research under grant F49620-97-1-0139, and by the National Science Foundation under grant CCR-96-23356. Research sponsored by the National Science Foundation under grant CCR-96-23356.     

Using Strassen's algorithm to accelerate the solution of linear systems

Strassen's algorithm for fast matrix-matrix multiplication has been implemented for matrices of arbitrary shapes on the CRAY-2 and CRAY Y-MP supercomputers. Several techniques have been used to reduce the scratch space requirement for this algorithm while simultaneously preserving a high level of performance. When the resulting Strassen-based matrix multiply routine is combined with some routines from the new LAPACK library, LU decomposition can be performed with rates significantly higher than those achieved by conventional means. We succeeded in factoring a 2048 × 2048 matrix on the CRAY Y-MP at a rate equivalent to 325 MFLOPS.This work is supported through NASA Contract NAS 2-12961.     

Multitasking a Navier-Stokes algorithm on the CRAY-2

This paper presents the results of multitasking a Navier-Stokes algorithm on the CRAY-2. The algorithm is a compact difference scheme for the solution of the incompressible, two-dimensional, time-dependent Navier-Stokes equations. Two implementations of multitasking on the CRAY-2 are considered: macrotasking (parallelism at the subroutine level) and microtasking (parallelism at the do-loop level). These two techniques are briefly described. The implementation of the algorithm is discussed in relation to these techniques, and the results for three problem sizes are presented. The timing results for both techniques are, in general, comparable with differences ranging between 2% and 14%, depending on the problem size. The best achieved speedup in a dedicated environment is 3.62 for macrotasking and 3.32 for microtasking. The task granularity for both techniques is computed, and the synchronization costs are estimated. For macrotasks of granularity of up to 0.5 msec, microtasking outperformed macrotasking, while the latter outperformed the former for granularity of over one msec.This research was supported by NASA Contract No. NAS2-11555 while the author was an employee of Sterling Software under contract to the Numerical Aerodynamic Simulation Systems Divison at NASA Ames Research Center, Moffett Field, CA 94035.     

Formal Methods Technology Transfer: A View from NASA

Since 1988 NASA Langley Research Center has supported a formal methods research program. From its inception, a primary goal of the program has been to transfer formal methods technology into aerospace industries focusing on applications in commercial air transport. The overall program has been described elsewhere. This paper gives an account of the technology transfer strategy and its evolution.     

Finding the minimum weight IIS cover of an infeasible system of linear inequalities

Given an inconsistent set of inequalities Ax b, theirreducible inconsistent subsystems (IISs) designate subsets of the inequalities such that at least one member of each subset must be deleted in order to achieve a feasible system. By solving a set covering problem over the IISs, one can determine a minimum weight set of inequalities that must be deleted in order to achieve feasibility. Since the number of IISs is generally exponential in the size of the original subsystem, we generate the IISs only when they are violated by a trial solution. Computational results on the NETLIB infeasible LP library are given.This author was supported by Air Force Office of Scientific Research and Office of Naval Research Contract #F49620-92-J-0248-DEF.     

Tracing application program execution on the CRAY X-MP and CRAY-2

Important insights into program operation can be gained by observing dynamic execution behavior. Unfortunately, many high-performance machines provide execution profile summaries as the only tool for performance investigation. We have developed a tracing library for the CRAY X-MP and CRAY-2 supercomputers that supports the low-overhead capture of execution events for sequential and multitasked programs. This library has been extended to use the automatic instrumentation facilities on these machines, allowing trace data from routine entry and exit, and other program segments, to be captured. To assess the utility of the trace-based tools, three of the Perfect Benchmark codes have been tested in scalar and vector modes with the tracing instrumentation. In addition to computing summary execution statistics from the traces, interesting execution dynamics appear when studying the trace histories. It is also possible to model application performance based on properties identified from traces. Our conclusion is that adding tracing support in Cray supercomputers can have significant returns in improved performance characterization and evaluation.An earlier version of this paper was presented at Supercomputing '90.Supported in part by the National Science Foundation under Grants No. NSF MIP-88-07775 and No. NSF ASC-84-04556, and the NASA Ames Research Center Grant No. NCC-2-559.Supported in part by the National Science Foundation under grant NSF ASC-84-04556.Supported in part by the National Science Foundation under grants NSF CCR-86-57696, NSF CCR-87-06653 and NSF CDA-87-22836 and by the National Aeronautics and Space Administration under NASA Contract Number NAG-1-613.