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 793 records · Page 44

Demand Capacity Balancing at Vertiports for Initial Strategic Conflict Management of Urban Air Mobility Operations

Urban Air Mobility (UAM) is a new transportation concept that enables highly automated, cooperative, passenger or cargo-carrying air transportation services in and around urban areas. To achieve the high level of operational density and complexity desired by the UAM community, an airspace system that allows UAM operators to readily access and operate safely and efficiently in the airspace is needed. This airspace system will require air traffic management designed to reduce the risk of conflicts and loss of separation between UAM flights. In general, strategic conflict management is considered as the first layer of conflict management for safe flight operations to condition the traffic to reduce the need for airborne separation provision, the second layer of conflict management. Demand Capacity Balancing (DCB) is one of the concept components to achieve strategic conflict management. DCB strategically evaluates traffic demand and resource capacities to allow UAM operators to determine when, where and how they operate, while mitigating conflicting needs for airspace and vertiport capacity. DCB can be applied whenever UAM demand exceeds the capacity in airspace or at vertiports. As the UAM ecosystem evolves with advanced technologies and matured operational procedures, more complicated conflict management will likely be needed. In the current UAM ‘Concept of Operation (ConOps) 1.0’ operational stage defined by FAA, however, it will be meaningful to explore the demand capacity balancing at vertiports only, as an initial strategic conflict management approach for UAM operations because vertiport capacity seems to be a bottleneck of UAM traffic. For this research, we developed a demand-capacity imbalance detection and resolution service for UAM. This DCB service identifies the demand from operators and compares the demand to a given capacity at the shared resources (i.e., vertiports) over the upcoming time horizon which is divided into time bins having a constant interval. When a new flight plan is submitted, the algorithm embedded in the DCB service checks the available time bins based on the desired departure time and estimated arrival time at origin and destination vertiports, respectively. If the time bins for the originally desired times are already occupied by other flights (i.e., demand is at or above capacity), the algorithm finds the next available time bins for takeoff and landing and shifts the conflicting departure time to the earliest time that satisfies the capacity constraints at both origin and destination vertiports. The details of the algorithm will be described in the final manuscript. Figure 1 shows that the proposed DCB algorithm works well for a sample traffic scenario. In this example, a total of 144 flights, split between two operators, are planned over 2 hours, traveling 10 routes between five vertiports. In the heatmaps, the horizontal axis shows 12 time bins where each bin represents a 12-minute interval, and the vertical axis shows five vertiports. The number in each cell shows the number of operations, counting both departures and arrivals, at a specific vertiport in each time bin. For the given capacity of 2 operations/vertiport/bin, Figure 1 shows that the original demand sometimes exceeds the capacity, but the modified demand is reduced to the given capacity after resolving demand-capacity imbalances. When UAM flights are operated, it is expected that many practical issues would arise in the federated system architecture with multiple operators. UAM operators may experience a time synchronization issue due to communication delay between operator and vehicle. UAM vehicles would fly at different flight speeds, depending on vehicle models. Actual departure and arrival times can have large variations, compared to the schedule. The lead time from flight plan submission to desired departure time can vary by service type (e.g., regular shuttle service vs. on-demand service). Using the proposed DCB algorithm, we also investigated how the actual flight schedule and DCB performance are affected by these uncertainties such as unsynchronized times between operators, flight speed differences, lead time differences, and departure time errors. The final manuscript will include the background of this research work, the description of the DCB algorithm and its use cases with traffic scenarios. It will also provide the analytical results about the impact of various uncertainties that can occur in actual UAM operations on the DCB at vertiports, in terms of demand distribution changes, number of simultaneous operations, and delay propagation.

Urban Air Mobility↗

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.↗

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.↗

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.↗

A Multistep Probability of Collision Computation Algorithm

The two-dimensional probability of collision calculation method is both widely used and computationally efficient. However, Monte Carlo simulations show that this method sometimes fails to provide sufficiently accurate estimates for Earthorbiting satellites. This study presents a multistep algorithm that calculates collision probabilities for all conjunctions, regardless if affected by curvilinear trajectory or time varying covariance dynamics. The algorithm sequentially applies increasingly accurate estimation methods, but only as required for efficiency. Evaluating usage violations for the two-dimensional probability of collision method represents one of the most important steps. Extensive testing demonstrates the efficiency and reliability of the multistep algorithm.

Doyle T. Hall↗

Multi-time-step integration using nodal partitioning

An algorithm is presented which integrates different groups of nodes of a finite element mesh with different time steps and different integrators. Since the nodal groups are updated independently no unsymmetric systems need be solved. Stability is demonstrated by showing that an energy norm of the solution decreases after every update if the time step is less than a given critical value. The element eigenvalue inequality theorem is used to give the critical time step in terms of element eigenvalues.

Smolinski, P.↗

Zonal multigrid solution of compressible flow problems on unstructured and adaptive meshes

The simultaneous use of adaptive meshing techniques with a multigrid strategy for solving the 2-D Euler equations in the context of unstructured meshes is studied. To obtain optimal efficiency, methods capable of computing locally improved solutions without recourse to global recalculations are pursued. A method for locally refining an existing unstructured mesh, without regenerating a new global mesh is employed, and the domain is automatically partitioned into refined and unrefined regions. Two multigrid strategies are developed. In the first, time-stepping is performed on a global fine mesh covering the entire domain, and convergence acceleration is achieved through the use of zonal coarse grid accelerator meshes, which lie under the adaptively refined regions of the global fine mesh. Both schemes are shown to produce similar convergence rates to each other, and also with respect to a previously developed global multigrid algorithm, which performs time-stepping throughout the entire domain, on each mesh level. However, the present schemes exhibit higher computational efficiency due to the smaller number of operations on each level.

Mavriplis, Dimitri J.↗

An algorithm for obtaining the minimal realization of a linear time-invariant system and determining if a system is stabilizable-detectable

A definition of centralized fixed modes of a system, which is an adoption of the definition of fixed modes for a decentralized system is made. It is shown that the centralized fixed modes of a system can be easily and efficiently calculated in terms of the eigenvalues of the system, and that the calculation of such fixed modes enables one to determine, in a numerically efficient way, whether a system is controllable, observable, stabilizable, or detectable. An efficient algorithm for reducing a system to minimal realization form is then given. The algorithms have been effectively used on systems of order up to 100.

Davison, E. J.↗