Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

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

Basis functions for electronic structure calculations on spheres

We introduce a new basis function (the spherical Gaussian) for electronic structure calculations on spheres of any dimension D. We find general expressions for the one- and two-electron integrals and propose an efficient computational algorithm incorporating the Cauchy-Schwarz bound. Using numerical calculations for the D = 2 case, we show that spherical Gaussians are more efficient than spherical harmonics when the electrons are strongly localized.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

An Online Scheduling Algorithm with Advance Reservation for Large-Scale Data Transfers

Scientific applications and experimental facilities generate massive data sets that need to be transferred to remote collaborating sites for sharing, processing, and long term storage. In order to support increasingly data-intensive science, next generation research networks have been deployed to provide high-speed on-demand data access between collaborating institutions. In this paper, we present a practical model for online data scheduling in which data movement operations are scheduled in advance for end-to-end high performance transfers. In our model, data scheduler interacts with reservation managers and data transfer nodes in order to reserve available bandwidth to guarantee completion of jobs that are accepted and confirmed to satisfy preferred time constraint given by the user. Our methodology improves current systems by allowing researchers and higher level meta-schedulers to use data placement as a service where theycan plan ahead and reserve the scheduler time in advance for their data movement operations. We have implemented our algorithm and examined possible techniques for incorporation into current reservation frameworks. Performance measurements confirm that the proposed algorithm is efficient and scalable.

97 MATHEMATICS AND COMPUTING↗

A Rewriting-Based Approach to Trace Analysis

We present a rewriting-based algorithm for efficiently evaluating future time Linear Temporal Logic (LTL) formulae on finite execution traces online. While the standard models of LTL are infinite traces, finite traces appear naturally when testing and/or monitoring red applications that only run for limited time periods. The presented algorithm is implemented in the Maude executable specification language and essentially consists of a set of equations establishing an executable semantics of LTL using a simple formula transforming approach. The algorithm is further improved to build automata on-the-fly from formulae, using memoization. The result is a very efficient and small Maude program that can be used to monitor program executions. We furthermore present an alternative algorithm for synthesizing probably minimal observer finite state machines (or automata) from LTL formulae, which can be used to analyze execution traces without the need for a rewriting system, and can hence be used by observers written in conventional programming languages. The presented work is part of an ambitious runtime verification and monitoring project at NASA Ames, called PATHEXPLORER, and demonstrates that rewriting can be a tractable and attractive means for experimenting and implementing program monitoring logics.

Havelund, Klaus↗

Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation

Eigenvalue transformations, which include solving time-dependent differential equations as a special case, have a wide range of applications in scientific and engineering computation. While quantum algorithms for singular value transformations are well studied, eigenvalue transformations are distinct, especially for nonnormal matrices. Here, we propose an efficient quantum algorithm for performing a class of eigenvalue transformations that can be expressed as a certain type of matrix Laplace transformation. This allows us to significantly extend the recently developed linear combination of Hamiltonian simulation method [D. An, J.-P. Liu, and L. Lin, Phys. Rev. Lett., 131 (2023), 150603; D. An, A. M. Childs, and L. Lin, Commun. Math. Phys. 407, 19 (2026)] to represent a wider class of eigenvalue transformations, such as powers of the matrix inverse, 𝐴 −𝑘 , and the exponential of the matrix inverse, 𝑒 −𝐴 −1 . The latter can be interpreted as the solution of a mass-matrix differential equation of the form form 𝐴⁢𝑢′⁡⁡(𝑡) =−𝑢⁡(𝑡). We demonstrate that our eigenvalue transformation approach can solve this problem without explicitly inverting 𝐴, thereby reducing the computational complexity.

Laplace transform↗

Arbitrary-level hanging nodes for adaptive hphp-FEM approximations in 3D

In this paper we discuss constrained approximation with arbitrary-level hanging nodes in adaptive higher-order finite element methods (hphp-FEM) for three-dimensional problems. This technique enables using highly irregular meshes, and it greatly simplifies the design of adaptive algorithms as it prevents refinements from propagating recursively through the finite element mesh. The technique makes it possible to design efficient adaptive algorithms for purely hexahedral meshes. We present a detailed mathematical description of the method and illustrate it with numerical examples.

99 GENERAL AND MISCELLANEOUS↗

Improvement of parallelization efficiency of batch pattern BP training algorithm using Open MPI

The use of tuned collective's module of Open MPI to improve a parallelization efficiency of parallel batch pattern back propagation training algorithm of a multilayer perceptron is considered in this paper. The multilayer perceptron model and the usual sequential batch pattern training algorithm are theoretically described. An algorithmic description of a parallel version of the batch pattern training method is introduced. The obtained parallelization efficiency results using Open MPI tuned collective's module and MPICH2 are compared. Our results show that (i) Open MPI tuned collective's module outperforms MPICH2 implementation both on SMP computer and computational cluster and (ii) different internal algorithms of MPI_Allreduce() collective operation give better results on different scenarios and different parallel systems. Therefore the properties of the communication network and user application should be taken into account when a specific collective algorithm is used.

97 MATHEMATICS AND COMPUTING↗

Evaluation of Portable Acceleration Solutions for LArTPC Simulation Using Wire-Cell Toolkit

The Liquid Argon Time Projection Chamber (LArTPC) technology plays an essential role in many current and future neutrino experiments. Accurate and fast simulation is critical to developing efficient analysis algorithms and precise physics model projections. The speed of simulation becomes more important as Deep Learning algorithms are getting more widely used in LArTPC analysis and their training requires a large simulated dataset. Heterogeneous computing is an efficient way to delegate computationally intensive tasks to specialized hardware. However, as the landscape of compute accelerators quickly evolves, it becomes increasingly difficult to manually adapt the code to the latest hardware or software environments. A solution which is portable to multiple hardware architectures without substantially compromising performance would thus be very beneficial, especially for long-term projects such as the LArTPC simulations. In search of a portable, scalable and maintainable software solution for LArTPC simulations, we have started to explore high-level portable programming frameworks that support several hardware backends. In this paper, we present our experience porting the LArTPC simulation code in the Wire-Cell Toolkit to NVIDIA GPUs, first with the CUDA programming model and then with a portable library called Kokkos. Preliminary performance results on NVIDIA V100 GPUs and multi-core CPUs are presented, followed by a discussion of the factors affiecting the performance and plans for future improvements.

Yu, Haiwang↗

Quantum Algorithms for Representation-Theoretic Multiplicities

Kostka, Littlewood-Richardson, Plethysm, and Kronecker coefficients are the multiplicities of irreducible representations in the decomposition of representations of the symmetric group that play an important role in representation theory, geometric complexity, and algebraic combinatorics. We give quantum algorithms for computing these coefficients whenever the ratio of dimensions of the representations is polynomial. We show that there is an efficient classical algorithm for computing the Kostka numbers under this restriction and conjecture the existence of an analogous algorithm for the Littlewood-Richardson coefficients. We argue why such classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients and conjecture that our quantum algorithms lead to superpolynomial speedups. The conjecture about Kronecker coefficients was disproved by Panova [Polynomial time classical versus quantum algorithms for representation theoretic multiplicities, arXiv:2502.20253] with a classical algorithm which, if optimal, points to a 𝒪⁡(𝑛 4+2⁢𝑘 ) vs $\tilde{Ω}$⁡(𝑛 4⁢𝑘 2 +1 ) polynomial gap in quantum vs classical computational complexity for an integer parameter 𝑘.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

combinatorial optimization with demands (LDRD Final Report)

This report summarizes the research conducted and results obtained under the Laboratory Directed Research and Development (LDRD) project, “Combinatorial Optimization with Demands ,” from October 2010 to September 2012. Complex resource allocation problems are ubiquitous in mission-driven applications. We investigated resource allocation problems endowed with additional parameters called demands, which allow for richer modeling. Demand endowed resource allocation problems are considerably harder to solve than their traditional counterparts, and we developed a conceptually simple but powerful new framework called iterative packing which allowed us to address the added complexity of demands. By leveraging iterative packing , we designed approximation algorithms to solve a large class of hard resource allocation problems with demands. Approximation algorithms are efficient heuristics which also offer a performance guarantee on the worst case deviation from the cost of an optimal solution. Our algorithms offer better performance guarantees over previously known algorithms; moreover, we are able to show that our algorithms provide performance guarantees that are likely close to best possible.

Parekh, Ojas↗

A high-speed linear algebra library with automatic parallelism

Parallel or distributed processing is key to getting highest performance workstations. However, designing and implementing efficient parallel algorithms is difficult and error-prone. It is even more difficult to write code that is both portable to and efficient on many different computers. Finally, it is harder still to satisfy the above requirements and include the reliability and ease of use required of commercial software intended for use in a production environment. As a result, the application of parallel processing technology to commercial software has been extremely small even though there are numerous computationally demanding programs that would significantly benefit from application of parallel processing. This paper describes DSSLIB, which is a library of subroutines that perform many of the time-consuming computations in engineering and scientific software. DSSLIB combines the high efficiency and speed of parallel computation with a serial programming model that eliminates many undesirable side-effects of typical parallel code. The result is a simple way to incorporate the power of parallel processing into commercial software without compromising maintainability, reliability, or ease of use. This gives significant advantages over less powerful non-parallel entries in the market.

Boucher, Michael L.↗

Downlink Data Multiplexer

A multiplexer/demultiplexer system has been developed to enable the transmission, over a single channel, of four data streams generated by a variety of sources at different (including variable) bit rates. In the original intended application, replicas of this multiplexer/demultiplexer system would be incorporated into the spacecraft-to-ground communication systems of the space shuttles. The multiplexer of each system would be installed in the spacecraft, where it would acquire and process data from such sources as commercial digital camcorders, video tape recorders, and the spacecraft telemetry system. The demultiplexer of each system would be installed in a ground station. Purely terrestrial systems of similar design could be attractive for use in situations in which there are requirements to transmit multiple streams of high-quality video data and possibly other data over single channels. The figure is a block diagram of the multiplexer as configured to process data received via three fiber-optic channels like those of the International Space Station and one electrical-cable channel that conforms to the Institute of Electrical and Electronic Engineers (IEEE) 1394 standard. (This standard consists of specifications of a high-speed serial data interface, the physical layer of which includes a cable known in the art as "FireWire." An IEEE 1394 interface can also transfer power between the components to which it is connected.) The fiber-optic channels carry packet and/or bit-stream signals that conform to the standards of the Consultative Committee for Space Data Systems (CCSDS). The IEEE 1394 interface accepts an isochronous signal like that from a digital camcorder or a video tape recorder. The processing of the four input data streams to combine them into one output stream is governed by a statistical multiplexing algorithm that features a flow-control capability and makes it possible to utilize the transmission channel with nearly 100-percent efficiency. This algorithm allocates the available bandwidth of the transmission channel to the data streams according to a combination of data rates and preassigned priorities. Incoming data streams that demand too much bandwidth are blocked. Bandwidth not needed for a transmission of a given data stream is allocated to other streams as available. Priority is given to the IEEE 1394 stream. In addition to the four incoming data streams, the multiplexer transmits data on the status of the system. An operator can monitor and control the multiplexer via displays and controls on the multiplexer housing. The output of the multiplexer is connected via a coaxial cable with an impedance of 50 Ohms to an interface circuit compatible with the space-shuttle high-speed digital downlink, which operates at a rate of 48 Mb/s.

Holland, Douglas↗

Constraint treatment techniques and parallel algorithms for multibody dynamic analysis

Computational procedures for kinematic and dynamic analysis of three-dimensional multibody dynamic (MBD) systems are developed from the differential-algebraic equations (DAE's) viewpoint. Constraint violations during the time integration process are minimized and penalty constraint stabilization techniques and partitioning schemes are developed. The governing equations of motion, a two-stage staggered explicit-implicit numerical algorithm, are treated which takes advantage of a partitioned solution procedure. A robust and parallelizable integration algorithm is developed. This algorithm uses a two-stage staggered central difference algorithm to integrate the translational coordinates and the angular velocities. The angular orientations of bodies in MBD systems are then obtained by using an implicit algorithm via the kinematic relationship between Euler parameters and angular velocities. It is shown that the combination of the present solution procedures yields a computationally more accurate solution. To speed up the computational procedures, parallel implementation of the present constraint treatment techniques, the two-stage staggered explicit-implicit numerical algorithm was efficiently carried out. The DAE's and the constraint treatment techniques were transformed into arrowhead matrices to which Schur complement form was derived. By fully exploiting the sparse matrix structural analysis techniques, a parallel preconditioned conjugate gradient numerical algorithm is used to solve the systems equations written in Schur complement form. A software testbed was designed and implemented in both sequential and parallel computers. This testbed was used to demonstrate the robustness and efficiency of the constraint treatment techniques, the accuracy of the two-stage staggered explicit-implicit numerical algorithm, and the speed up of the Schur-complement-based parallel preconditioned conjugate gradient algorithm on a parallel computer.

Chiou, Jin-Chern↗

A distributed-memory approximation algorithm for maximum weight perfect bipartite matching

We design and implement an efficient parallel approximation algorithm for the problem of maximum weight perfect matching in bipartite graphs, i.e. the problem of finding a set of non-adjacent edges that covers all vertices and has maximum weight. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before factorization where sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64, are widely used due to the lack of scalable alternatives. To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then searches for weightaugmenting cycles of length four in parallel and iteratively augments the matching with a vertex disjoint set of such cycles. For most practical problems the weights of the perfect matchings generated by our algorithm are very close to the optimum. An efficient implementation of the algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer and can solve instances that are too large to be handled by a single node using the sequential algorithm.

Azad, Ariful↗

Convergence acceleration of implicit schemes in the presence of high aspect ratio grid cells

The performance of Navier-Stokes codes are influenced by several phenomena. For example, the robustness of the code may be compromised by the lack of grid resolution, by a need for more precise initial conditions or because all or part of the flowfield lies outside the flow regime in which the algorithm converges efficiently. A primary example of the latter effect is the presence of extended low Mach number and/or low Reynolds number regions which cause convergence deterioration of time marching algorithms. Recent research into this problem by several workers including the present authors has largely negated this difficulty through the introduction of time-derivative preconditioning. In the present paper, we employ the preconditioned algorithm to address convergence difficulties arising from sensitivity to grid stretching and high aspect ratio grid cells. Strong grid stretching is particularly characteristic of turbulent flow calculations where the grid must be refined very tightly in the dimension normal to the wall, without a similar refinement in the tangential direction. High aspect ratio grid cells also arise in problems that involve high aspect ratio domains such as combustor coolant channels. In both situations, the high aspect ratio cells can lead to extreme deterioration in convergence. It is the purpose of the present paper to address the reasons for this adverse response to grid stretching and to suggest methods for enhancing convergence under such circumstances. Numerical algorithms typically possess a maximum allowable or optimum value for the time step size, expressed in non-dimensional terms as a CFL number or vonNeumann number (VNN). In the presence of high aspect ratio cells, the smallest dimension of the grid cell controls the time step size causing it to be extremely small, which in turn results in the deterioration of convergence behavior. For explicit schemes, this time step limitation cannot be exceeded without violating stability restrictions of the scheme. On the other hand, for implicit schemes, which are typically unconditionally stable, there appears to be room for improvement through careful tailoring of the time step definition based on results of linear stability analyses. In the present paper, we focus on the central-differenced alternating direction implicit (ADI) scheme. The understanding garnered from this analyses can then be applied to other implicit schemes. In order to systematically study the effects of aspect ratio and the methods of mitigating the associated problems, we use a two pronged approach. We use stability analyses as a tool for predicting numerical convergence behavior and numerical experiments on simple model problems to verify predicted trends. Based on these analyses, we determine that efficient convergence may be obtained at all aspect ratios by getting a combination of things right. Primary among these are the proper definition of the time step size, proper selection of viscous preconditioner and the precise treatment of boundary conditions. These algorithmic improvements are then applied to a variety of test cases to demonstrate uniform convergence at all aspect ratios.

Buelow, B. E. O.↗

Hybrid quantum-classical algorithms for approximate graph coloring

We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX- k -CUT, the problem of finding an approximate k -vertex coloring of a graph. We compare this proposal to the best known classical and hybrid classical-quantum algorithms. First, we show that the standard (non-recursive) QAOA fails to solve this optimization problem for most regular bipartite graphs at any constant level p : the approximation ratio achieved by QAOA is hardly better than assigning colors to vertices at random. Second, we construct an efficient classical simulation algorithm which simulates level- 1 QAOA and level- 1 RQAOA for arbitrary graphs. In particular, these hybrid algorithms give rise to efficient classical algorithms, and no benefit arising from the use of quantum mechanics is to be expected. Nevertheless, they provide a suitable testbed for assessing the potential benefit of hybrid algorithm: We use the simulation algorithm to perform large-scale simulation of level- 1 QAOA and RQAOA with up to 300 qutrits applied to ensembles of randomly generated 3 -colorable constant-degree graphs. We find that level- 1 RQAOA is surprisingly competitive: for the ensembles considered, its approximation ratios are often higher than those achieved by the best known generic classical algorithm based on rounding an SDP relaxation. This suggests the intriguing possibility that higher-level RQAOA may be a potentially useful algorithm for NISQ devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Parallel Architecture For Robotics Computation

Universal Real-Time Robotic Controller and Simulator (URRCS) is highly parallel computing architecture for control and simulation of robot motion. Result of extensive algorithmic study of different kinematic and dynamic computational problems arising in control and simulation of robot motion. Study led to development of class of efficient parallel algorithms for these problems. Represents algorithmically specialized architecture, in sense capable of exploiting common properties of this class of parallel algorithms. System with both MIMD and SIMD capabilities. Regarded as processor attached to bus of external host processor, as part of bus memory.

Fijany, Amir↗

A comparison of two formulations for high-order accurate essentially non-oscillatory schemes

The finite-volume and finite-difference implementations of high-order accurate essentially nonoscillatory shock-capturing schemes are discussed and compared. Results obtained with fourth-order accurate algorithms based on both formulations are examined for accuracy, sensitivity to grid irregularities, resolution of waves that are oblique to the mesh, and computational efficiency. Some algorithm modifications that may be required for a given application are suggested. Conclusions that pertain to the relative merits of both formulations are drawn, and some circumstances for which each might be useful are noted.

Casper, J.↗

A comparison of two formulations for high-order accurate essentially non-oscillatory schemes

The finite-volume and finite-difference implementations of high-order accurate essentially non-oscillatory shock-capturing schemes are discussed and compared. Results obtained with fourth-order accurate algorithms based on both formulations are examined for accuracy, sensitivity to grid irregularities, resolution of waves that are oblique to the mesh, and computational efficiency. Some algorithm modifications that may be required for a given application are suggested. Conclusions that pertain to the relative merits of both formulations are drawn, and some circumstances for which each might be useful are noted.

Casper, Jay↗