«A Thesis Presented to The Academic Faculty by Nitin Arora In Partial Fulﬁllment of the Requirements for the Degree Doctor of Philosophy in the ...»
HIGH PERFORMANCE ALGORITHMS TO IMPROVE
THE RUNTIME COMPUTATION OF SPACECRAFT
The Academic Faculty
In Partial Fulﬁllment
of the Requirements for the Degree
Doctor of Philosophy in the
Guggenheim School of Aerospace Engineering
Georgia Institute of Technology
Copyright c 2013 by Nitin Arora
HIGH PERFORMANCE ALGORITHMS TO IMPROVE
THE RUNTIME COMPUTATION OF SPACECRAFT
Dr. Ryan P. Russell, Advisor Dr. Richard Vuduc The Department of Aerospace School of Computational Science and Engineering and Engineering Engineering Mechanics Georgia Institute of Technology The University of Texas at Austin Dr. Robert D. Braun (co-advisor) Dr. P.K Yeung Guggenheim School of Aerospace Guggenheim School of Aerospace Engineering Engineering Georgia Institute of Technology Georgia Institute of Technology Dr. Marcus J. Holzinger Date Approved: June-27-2013 Guggenheim School of Aerospace Engineering Georgia Institute of Technology “I can live with doubt and uncertainty. I think it’s much more interesting to live not knowing than to have answers which might be wrong.” Richard P. Feynman iii Dedicated to mom and dad who always believed in me iv
ACKNOWLEDGEMENTSFirst of all, I would like to thank my advisor Dr. Ryan Russell for his understanding and support throughout my graduate studies. Thank you, Ryan for giving me an opportunity to work with you. Your patience, ingenuity, clear vision, and positive criticism have enriched my experience as a graduate student. Thank you for putting up with me even when I wasnt the easiest student to advice.
I would also like to acknowledge my committee members for their invaluable inputs and support over the course of my research. Dr. Robert Braun, apart from your wise and invaluable research advice, I would like to thank you for helping me stay in the lab as your student towards the end of my graduate studies. Dr. Rich Vuduc, I am really grateful to you for introducing me to the world of high performance computing and allowing me to be a part of your lab. I enjoyed our quick afternoon meetings, where I always ended up learning something new. Dr. Marcus Holzinger, thank you for allowing me to be your teaching assistant and for your valuable advisement while being a part of my research committee. Dr. P.K Yeung, I am very grateful for your unique perspective on my research and for your valuable inputs as my committee member. I would also like to acknowledge the graduate coordinator of the School of Aerospace Engineering, Dr. Jeﬀ Jagoda. Your continuous support has helped me sail through many troubled waters, thanks a lot!
Being part of the Space Systems Design Lab and school of Aerospace Engineering at Georgia Tech has left me with a lot of fond memories. From qualiﬁers to my thesis defense, I have always enjoyed the continuous support and constructive criticism from my fellow labmates and friends. Particularly, I would like to thank Gregory Lantoine, Brad Steinfeldt, Richard Otero, Jean-Francois Castet, Nuno Filipe, Francesca Favaro,
needed support at Georgia Tech. I cannot forget my fellow labmates at the University of Texas at Austin. Thanks a lot Vivek Vittaldev, Demyan Lantukh and Etienne Pellegrini for putting up with me. Best of luck to you all!
I would also like to take this opportunity to acknowledge NASA, Air Force Research Lab and Emergent for supporting the work presented in this thesis. I would also like to acknowledge some of the people at the Jet Propulsion Laboratory who made my internship experience really special and helped me gain conﬁdence as a researcher.
Thanks a lot Nathan J. Strange, Farah Alibay, Julim Lee, Francesco Simeoni, Jeffery Stuart, Damon Landau, Anastassios E. Petropoulos, Gregory J. Whiﬀen, Daniel Grebow, Jon A. Sims, Antranik Kolanjian and Shyam Bhaskaran.
I would like to thank all my close friends back in India and here in the US. I have known some for more than 10 years while there are others that I have met during my time at Georgia Tech. I would like to especially thank Ankur Bajoria, Rishab Mahajan, Abhijit Kamra, Akaash Jain, Nikhil Nanda, Shashank Shekhar Singhal, Amit Sharma, Saurabh Nagpal, Rajan Arora, Siddharth Sharma and Aditya Bhatt for bearing with me for past 5+ years. All of you are absolutely amazing! Prabuddha Bansal, thanks a lot for the competitive and fun-ﬁlled squash games we played over the past ﬁve years. Divya Bhatia, I have enjoyed all the arguments and our various discussion about the universe. Thanks for putting up with me. Kiran Girdhar, thanks a lot for always being there for me. I really enjoyed your impromptu weekend trips to Atlanta. Shaloo Rakheja, I really cherished the time we spent together at Georgia Tech. Saying that we have been through a lot together is an understatement. Thanks a lot for you care, support and the continuous reminders about my terrible English.
I would also like to acknowledge the Star Trek franchise for the wonder, joy, and motivation it provided me during those long working hours.
Finally, I would give like to give a special thank you to my Mom, Dad and my
me rise above my best. Mom and Dad, thanks for believing in my dreams. You are the best! Rohan, thanks for being the best younger brother, you rock!
xvii 80 Speedup for complete STM plus STT computation.......... 136 81 General Algorithmic Model....................... 142 Case 1: Scaled speedup, RKF-54, SPICE, 70 × 70 SH ﬁeld...... 151 Case 1: Scaled speedup, RKF-54, SPICE, 156 × 156 SH ﬁeld..... 151 Case 1: Scaled speedup, RKF-54, SPICE, 360 × 360 SH ﬁeld..... 152 Case 1: Scaled speedup, RKF-54, FIRE, 70 × 70 SH ﬁeld....... 152 Case 1: Scaled speedup, RKF-54, FIRE, 156 × 156 SH ﬁeld...... 153 Case 1: Scaled speedup, RKF-54, FIRE, 360 × 360 SH ﬁeld...... 154 Case 1: Scaled speedup, DOPRI-78, SPICE, 70 × 70 SH ﬁeld..... 154 Case 1: Scaled speedup, DOPRI-78, SPICE, 156 × 156 SH ﬁeld... 155 Case 1: Scaled speedup, DOPRI-78, SPICE, 360 × 360 SH ﬁeld... 155 Case 1: Scaled speedup, DOPRI-78, FIRE, 70 × 70 SH ﬁeld..... 156 Case 1: Scaled speedup, DOPRI-78, FIRE, 156 × 156 SH ﬁeld.... 156 Case 1: Scaled speedup, DOPRI-78, FIRE, 360 × 360 SH ﬁeld.... 157 Case 2: Scaled speedup, RKF-54, SPICE, 70 × 70 SH ﬁeld...... 158 Case 2: Scaled speedup, RKF-54, SPICE, 156 × 156 SH ﬁeld..... 158 Case 2: Scaled speedup, RKF-54, SPICE, 360 × 360 SH ﬁeld..... 159 Case 2: Scaled speedup, RKF-54, FIRE, 70 × 70 SH ﬁeld....... 159 Case 2: Scaled speedup, RKF-54, FIRE, 156 × 156 SH ﬁeld...... 160 Case 2: Scaled speedup, RKF-54, FIRE, 360 × 360 SH ﬁeld...... 161 100 Case 2: Scaled speedup, DOPRI-78, SPICE, 70 × 70 SH ﬁeld..... 161 101 Case 2: Scaled speedup, DOPRI-78, SPICE, 156 × 156 SH ﬁeld... 162 102 Case 2: Scaled speedup, DOPRI-78, SPICE, 360 × 360 SH ﬁeld... 162 103 Case 2: Scaled speedup, DOPRI-78, FIRE, 70 × 70 SH ﬁeld..... 163 104 Case 2: Scaled speedup, DOPRI-78, FIRE, 156 × 156 SH ﬁeld.... 163 105 Case 2: Scaled speedup, DOPRI-78, FIRE, 360 × 360 SH ﬁeld.... 164 106 Case 1: absolute runtime (sec), 70 × 70 SH ﬁeld............ 165 107 Case 2: absolute runtime (sec), 70 × 70 SH ﬁeld............ 165 108 Case 1: absolute runtime (sec), 156 × 156 SH ﬁeld........... 166
Increasing space mission complexity coupled with challenging science requirements are driving the need for fast and robust space trajectory design and simulation tools.
Current state-of-the art methods and techniques are often found to be lacking, particularly when problems are scaled to the future demands of mission design.
This challenging problem is addressed in this thesis by 1) identifying a set of high impact “building-block” astrodynamics algorithms, 2) systematically improving several current state-of-the art solution methods via theoretical and methodological improvements and 3) taking advantage of modern computational hardware and numerical techniques to provide signiﬁcant improvements in speed and robustness. In this thesis, ﬁve high impact astrodynamics problems are identiﬁed and their algorithms are selected for improvement. The solutions to the selected problems have applications ranging from preliminary mission design to high-ﬁdelity space trajectory design and simulation.
The ﬁrst problem identiﬁed is the multiple-revolution Lambert problem. Lambert’s problem is one of the most extensively studied problems in space-ﬂight mechanics and enjoys a large volume of research, spanning over several decades. In this thesis, a new formulation of the multiple revolution Lambert problem is presented.
The formulation is based on a cosine transformation and uses rational functions for generating accurate initial guesses. Thanks to a new geometry based parameter, the resulting formulation is simpliﬁed and only requires one auxiliary function to handle the separate forms of the conic. Apart from enjoying 40% to 60% reduction in runtime over the current state-of-the art Gooding’s method, the new formulation also
High-ﬁdelity perturbation models are one of the major speed bottlenecks encountered during spacecraft trajectory design and simulation. The current work attempts to improve the performance of two aspects of these perturbation models, namely, the high-ﬁdelity geopotential evaluation and the accurate ephemeris computation.
High-ﬁdelity geopotentials are typically computed via spherical harmonics, which is slow and non-intuitive to implement eﬃciently. In this thesis a new model called Fetch is proposed. Fetch is designed to take advantage of all the previous methods in the literature, while ﬁnding innovative solutions to correct their respective problems.
The model is based on a modiﬁcation to the Junkins weighting function method and achieves up to three orders of magnitude in speedup over the conventional spherical harmonics approach. As a part of this thesis, the Fetch model is applied to interpolate the GRACE GGM03C gravity model. Four Fetch models with diﬀerent spherical harmonic degrees and order are computed and archived.
The next problem that deserves attention is the computation of accurate solar system body state and orientation data. The current work attempts to solve this problem by proposing a new ephemeris system called FIRE (Fast Interpolated Runtime Ephemeris). FIRE is custom designed for space trajectory applications that favor speed and smooth derivatives. It relies on spline interpolation and is based on a multi-level computation architecture. FIRE is demonstrated to be 50 to 70 times faster (compared to JPL’s SPICE system) for typical trajectory applications while still achieving high accuracy. The speed is gained in exchange for a modest memory burden, which is necessary for the interpolation coeﬃcients.
Shifting the focus to applications that require partial derivatives of a ﬁnal state with respect to an initial state; the thesis also investigates the problem of fast sensitivity computation. Sensitivity information is used by many batch and sequential ﬁltering applications, gradient based optimization algorithms, and is applied in a wide
tivity computation across a single trajectory. A new hybrid parallelization strategy is proposed, utilizing the Central Processing Unit (CPU) and the Graphics Processing Unit (GPU) to achieve rapid sensitivity computation on a single workstation. For example, trajectory propagation with overlapped computations demonstrate that ﬁrst order sensitivities are calculated almost for free when compared to the conventional CPU implementation. The proposed technique can be applied to various optimization methods like optimal control, parameter optimization and other gradient based techniques.