Search NASA⌕ Search

SEARCH · Search NASA

Results for “algorithm timings”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 1,603 records · Page 89

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 efficient 0(nlogn + m) time implementation of the Sloan algorithm, where n is the number of rows (vertices), and m 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 Reverse Cuthill-Mckee 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.

Kumfert, Gary↗

SPEEDES - A multiple-synchronization environment for parallel discrete-event simulation

Synchronous Parallel Environment for Emulation and Discrete-Event Simulation (SPEEDES) is a unified parallel simulation environment. It supports multiple-synchronization protocols without requiring users to recompile their code. When a SPEEDES simulation runs on one node, all the extra parallel overhead is removed automatically at run time. When the same executable runs in parallel, the user preselects the synchronization algorithm from a list of options. SPEEDES currently runs on UNIX networks and on the California Institute of Technology/Jet Propulsion Laboratory Mark III Hypercube. SPEEDES also supports interactive simulations. Featured in the SPEEDES environment is a new parallel synchronization approach called Breathing Time Buckets. This algorithm uses some of the conservative techniques found in Time Bucket synchronization, along with the optimism that characterizes the Time Warp approach. A mathematical model derived from first principles predicts the performance of Breathing Time Buckets. Along with the Breathing Time Buckets algorithm, this paper discusses the rules for processing events in SPEEDES, describes the implementation of various other synchronization protocols supported by SPEEDES, describes some new ones for the future, discusses interactive simulations, and then gives some performance results.

Steinman, Jeff S.↗

Efficient Measurement-Driven Eigenenergy Estimation with Classical Shadows

Quantum algorithms exploiting real-time evolution under a target Hamiltonian have demonstrated remarkable efficiency in extracting key spectral information. However, the broader potential of these methods, particularly beyond ground-state calculations, is underexplored. In this work, we introduce the framework of multiobservable dynamic mode decomposition (MODMD), which combines the observable dynamic mode decomposition (DMD), a measurement-driven eigensolver tailored for near-term implementation, with classical shadow tomography. MODMD leverages random scrambling in the classical shadow technique to construct, with exponentially reduced resource requirements, a signal subspace that encodes rich spectral information. Notably, we replace typical Hadamard-test circuits with a protocol designed to predict low-rank observables, thereby broadening the use of classical shadow tomography for predicting many low-rank observables. We establish theoretical guarantees on the spectral approximation from MODMD, taking into account distinct sources of error. In the ideal case, we prove that the spectral error scales as exp (−Δ⁢𝐸⁢𝑡 max ), where Δ⁢𝐸 is the Hamiltonian spectral gap and 𝑡 max is the maximal simulation time. This analysis provides a rigorous justification of the rapid convergence observed across simulations. To demonstrate the utility of our framework, we consider its application to fundamental tasks, such as determining the low-lying, i.e., ground or excited, energies of representative many-body systems. Our work paves the path for efficient designs of measurement-driven algorithms on near-term and early fault-tolerant quantum devices.

quantum algorithms & computation↗

A time-accurate implicit method for chemically reacting flows at all Mach numbers

The objective of this work is to develop a unified solution algorithm capable of treating time-accurate chemically reacting flows at all Mach numbers, ranging from molecular diffusion velocities to supersonic speeds. A rescaled pressure term is used in the momentum equation to circumvent the singular behavior of pressure at low Mach numbers. A dual time-stepping integration procedure is established. The system eigenvalues become well behaved and have the same order of magnitude, even in the very low Mach number regime. The computational efficiency for moderate and high speed flow is competitive with the conventional density-based scheme. The capabilities of the algorithm are demonstrated by applying it to selected model problems including nozzle flows and flame dynamics.

Withington, J. P.↗

Towards a Framework for Evaluating and Comparing Diagnosis Algorithms

Diagnostic inference involves the detection of anomalous system behavior and the identification of its cause, possibly down to a failed unit or to a parameter of a failed unit. Traditional approaches to solving this problem include expert/rule-based, model-based, and data-driven methods. Each approach (and various techniques within each approach) use different representations of the knowledge required to perform the diagnosis. The sensor data is expected to be combined with these internal representations to produce the diagnosis result. In spite of the availability of various diagnosis technologies, there have been only minimal efforts to develop a standardized software framework to run, evaluate, and compare different diagnosis technologies on the same system. This paper presents a framework that defines a standardized representation of the system knowledge, the sensor data, and the form of the diagnosis results and provides a run-time architecture that can execute diagnosis algorithms, send sensor data to the algorithms at appropriate time steps from a variety of sources (including the actual physical system), and collect resulting diagnoses. We also define a set of metrics that can be used to evaluate and compare the performance of the algorithms, and provide software to calculate the metrics.

Kurtoglu, Tolga↗

Calculation of power spectrums from digital time series with missing data points

Two algorithms are developed for calculating power spectrums from the autocorrelation function when there are missing data points in the time series. Both methods use an average sampling interval to compute lagged products. One method, the correlation function power spectrum, takes the discrete Fourier transform of the lagged products directly to obtain the spectrum, while the other, the modified Blackman-Tukey power spectrum, takes the Fourier transform of the mean lagged products. Both techniques require fewer calculations than other procedures since only 50% to 80% of the maximum lags need be calculated. The algorithms are compared with the Fourier transform power spectrum and two least squares procedures (all for an arbitrary data spacing). Examples are given showing recovery of frequency components from simulated periodic data where portions of the time series are missing and random noise has been added to both the time points and to values of the function. In addition the methods are compared using real data. All procedures performed equally well in detecting periodicities in the data.

Murray, C. W., Jr.↗

Parallel matrix multiplication on the Connection Machine

Matrix multiplication is a computation and communication intensive problem. Six parallel algorithms for matrix multiplication on the Connection Machine are presented and compared with respect to their performance and processor usage. For n by n matrices, the algorithms have theoretical running times of O(n to the 2nd power log n), O(n log n), O(n), and O(log n), and require n, n to the 2nd power, n to the 2nd power, and n to the 3rd power processors, respectively. With careful attention to communication patterns, the theoretically predicted runtimes can indeed be achieved in practice. The parallel algorithms illustrate the tradeoffs between performance, communication cost, and processor usage.

Tichy, Walter F.↗

THE QUASIPERIODIC AUTOMATED TRANSIT SEARCH ALGORITHM

We present a new algorithm for detecting transiting extrasolar planets in time-series photometry. The Quasiperiodic Automated Transit Search (QATS) algorithm relaxes the usual assumption of strictly periodic transits by permitting a variable, but bounded, interval between successive transits. We show that this method is capable of detecting transiting planets with significant transit timing variations without any loss of significance-{sup s}mearing{sup -}as would be incurred with traditional algorithms; however, this is at the cost of a slightly increased stochastic background. The approximate times of transit are standard products of the QATS search. Despite the increased flexibility, we show that QATS has a run-time complexity that is comparable to traditional search codes and is comparably easy to implement. QATS is applicable to data having a nearly uninterrupted, uniform cadence and is therefore well suited to the modern class of space-based transit searches (e.g., Kepler, CoRoT). Applications of QATS include transiting planets in dynamically active multi-planet systems and transiting planets in stellar binary systems.

79 ASTRONOMY AND ASTROPHYSICS↗

Parallel adaptive fluid-structure interaction simulation of explosions impacting on building structures

We pursue a level set approach to couple an Eulerian shock-capturing fluid solver with space-time refinement to an explicit solid dynamics solver for large deformations and fracture. The coupling algorithms considering recursively finer fluid time steps as well as overlapping solver updates are discussed in detail. Our ideas are implemented in the AMROC adaptive fluid solver framework and are used for effective fluid-structure coupling to the general purpose solid dynamics code DYNA3D. Beside simulations verifying the coupled fluid-structure solver and assessing its parallel scalability, the detailed structural analysis of a reinforced concrete column under blast loading and the simulation of a prototypical blast explosion in a realistic multistory building are presented.

Deiterding, Ralf↗

Optimizing Approximate Weighted Matching on Nvidia Kepler K40

Matching is a fundamental graph problem with numerous applications in science and engineering. While algorithms for computing optimal matchings are difficult to parallelize, approximation algorithms on the other hand generally compute high quality solutions and are amenable to parallelization. In this paper, we present efficient implementations of the current best algorithm for half-approximate weighted matching, the Suitor algorithm, on Nvidia Kepler K-40 platform. We develop four variants of the algorithm that exploit hardware features to address key challenges for a GPU implementation. We also experiment with different combinations of work assigned to a warp. Using an exhaustive set of $269$ inputs, we demonstrate that the new implementation outperforms the previous best GPU algorithm by $10$ to $100\times$ for over $100$ instances, and from $100$ to $1000\times$ for $15$ instances. We also demonstrate up to $20\times$ speedup relative to $2$ threads, and up to $5\times$ relative to $16$ threads on Intel Xeon platform with $16$ cores for the same algorithm. The new algorithms and implementations provided in this paper will have a direct impact on several applications that repeatedly use matching as a key compute kernel. Further, algorithm designs and insights provided in this paper will benefit other researchers implementing graph algorithms on modern GPU architectures.

GPU↗

Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems

We investigate the limitations of quantum computers for solving nonlinear dynamical systems. In particular, we tighten the worst-case bounds of the quantum Carleman linearisation (QCL) algorithm answering one of their open questions. We provide a further significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector. Given a natural choice of coordinates for a dynamical system with one or more positive Lyapunov exponents and solutions that grow sub-exponentially, we prove that any such algorithm has complexity scaling at least exponentially in the integration time. As such, an efficient quantum algorithm for simulating chaotic systems or regimes is likely not possible.

97 MATHEMATICS AND COMPUTING↗

A rapid implicit-explicit solution to the two-dimensional time dependent incompressible Navier-Stokes equations

A second-order time-accurate and spatially factored algorithm was used in a finite difference scheme for the numerical solution of the time-dependent, incompressible, two dimensional Navier-Stokes equations in conservation-law form using vorticity and stream function variables. The systems of equations are solved at each time step by an iterative technique. Numerical results were obtained for a circular cylinder at a Reynolds number of 15, and an NACA 0012 airfoil at zero angle of attack at Reynolds numbers of 10 to the third and 10 to the fourth powers. The results are in agreement with another numerical technique, and the computing time required to obtain the steady state solution at the Reynolds number of 10 to the 4th power was 49.7 sec on CDC 7600 computer using a 65 x 84 computational grind.

Davis, J. E.↗

Dynamic large deflection response of composite laminates subjected to impact

Impact responses of composite laminates with and without initial stresses are investigated using the finite element method. A nine-node isoparametric quadrilateral element based on the Mindlin plate theory and the von Karman large deflection assumptions is developed. An experimentally established contact law which accounts for the permanent indentation is incorporated into the finite element program to evaluate the impact force. In the time integration, the Newmark constant acceleration algorithm is used in conjunction with successive iterations within each time step. Numerical results, including the contact force histories, deflections and strains in the plate, are presented.

Chen, J. K.↗

Extension and applications of flux-vector splitting to unsteady calculations on dynamic meshes

The Van Leer method of flux-vector splitting for the Euler equations is extended for use on moving meshes and all the properties of the original splittings are maintained. The solution is advanced in time with an implicit, approximately factored algorithm. The use of multiple grids to reduce the computer time is investigated. A substantial reduction in computer time to resolve a pitching cycle is easily obtained with virtually no loss in accuracy. A subiterative procedure to eliminate factorization and linearization errors so that larger time steps can be used is also investigated. Subsequent computations show good agreement with experimental data for transonic and supersonic airfoils and wings undergoing forced pitching oscillation.

Anderson, W. Kyle↗

An efficient algorithm for computing the crossovers in satellite altimetry

An efficient algorithm has been devised to compute the crossovers in satellite altimetry. The significance of the crossovers is twofold. First, they are needed to perform the crossover adjustment to remove the orbit error. Secondly, they yield important insight into oceanic variability. Nevertheless, there is no published algorithm to make this very time consuming task easier, which is the goal of this report. The success of the algorithm is predicated on the ability to predict (by analytical means) the crossover coordinates to within 6 km and 1 sec of the true values. Hence, only one interpolation/extrapolation step on the data is needed to derive the crossover coordinates in contrast to the many interpolation/extrapolation operations usually needed to arrive at the same accuracy level if deprived of this information.

Tai, Chang-Kou↗

A Lanczos algorithm for vibration, suckling and termal analysis

This paper reviews an eigensolver algorithm based on the Lanczos Method for vibration, buckling and thermal analysis. The original code was written for inclusion in the Computational Mechanics Testbed (COMET), a general purpose finite element code. A portable version of the Lanczos code that is optimized for high-performance supercomputers has been developed. Special features of the algorithm include the capability to compute rigid body modes, thermal modes and Lanczos vectors that are derived from the applied load vector. The latter is necessary when using the Lanczos vectors as reduced-basis vectors in transient structural response and transient heat conduction calculations. The modularity of the code allows the user the option of including the most up-to-date utilities, such as the equation solver best suited for the application. The algorithm is discussed in detail and results of several applications are presented. Timing results for a vibration application indicate that the Lanczos algorithm is twenty times faster than the subspace iteration method which has been extensively used in the past.

Bostic, Susan W.↗

Parallel O(log n) algorithms for open- and closed-chain rigid multibody systems based on a new mass matrix factorization technique

In this paper, parallel O(log n) algorithms for computation of rigid multibody dynamics are developed. These parallel algorithms are derived by parallelization of new O(n) algorithms for the problem. The underlying feature of these O(n) algorithms is a drastically different strategy for decomposition of interbody force which leads to a new factorization of the mass matrix (M). Specifically, it is shown that a factorization of the inverse of the mass matrix in the form of the Schur Complement is derived as M(exp -1) = C - B(exp *)A(exp -1)B, wherein matrices C, A, and B are block tridiagonal matrices. The new O(n) algorithm is then derived as a recursive implementation of this factorization of M(exp -1). For the closed-chain systems, similar factorizations and O(n) algorithms for computation of Operational Space Mass Matrix lambda and its inverse lambda(exp -1) are also derived. It is shown that these O(n) algorithms are strictly parallel, that is, they are less efficient than other algorithms for serial computation of the problem. But, to our knowledge, they are the only known algorithms that can be parallelized and that lead to both time- and processor-optimal parallel algorithms for the problem, i.e., parallel O(log n) algorithms with O(n) processors. The developed parallel algorithms, in addition to their theoretical significance, are also practical from an implementation point of view due to their simple architectural requirements.

Fijany, Amir↗

The applicability of turbulence models to aerodynamic and propulsion flowfields at McDonnell-Douglas Aerospace

The objective of this viewgraph presentation is to evaluate turbulence models for integrated aircraft components such as the forebody, wing, inlet, diffuser, nozzle, and afterbody. The one-equation models have replaced the algebraic models as the baseline turbulence models. The Spalart-Allmaras one-equation model consistently performs better than the Baldwin-Barth model, particularly in the log-layer and free shear layers. Also, the Sparlart-Allmaras model is not grid dependent like the Baldwin-Barth model. No general turbulence model exists for all engineering applications. The Spalart-Allmaras one-equation model and the Chien k-epsilon models are the preferred turbulence models. Although the two-equation models often better predict the flow field, they may take from two to five times the CPU time. Future directions are in further benchmarking the Menter blended k-w/k-epsilon and algorithmic improvements to reduce CPU time of the two-equation model.

Kral, Linda D.↗