Two Case Studies of Reversibility in Computational Methods

Abstract

Currently state- saving is employed in many large simulations to realize rollback. Reverse computation is a recently proposed method which computes previous states instead of saving them. This approach can be beneficial on large machines as computing power is abundantly available and is possibly more efficient than retrieval from memory. This project investigates the reversibility of the well known Newton- Raphson root finding method and the possibility of developing a reversible interface for the Level 1 (vector) operations found in the Basic Linear Algebra Subprograms (BLAS) library. The mechanics of Newton- Raphson were studied and an algorithm was developed to reverse each iteration in the forward method. The reverse method involves finding the root of a derived function and forward Newton-Raphson is used on the derived function. Consequently, reverse Newton-Raphson gains the strengths and weaknesses found in Newton-Raphson. The reverse method has produced favorable results on functions that converge with forward Newton-Raphson. Unfortunately the forward method behaves unpredictably when multiple roots, periodic behavior, local minima, etc. exist in the target function and the reverse method will also produce unpredictable behavior in these cases. Further research is needed to handle unpredictability in certain functions in the reverse method. Routines in the BLAS Level 1 were analyzed and candidates were chosen based on the need for reversibility. Only those routines which modify input values require reversal. Reverse routines were developed for Givens rotation, vector scale, vector swap, and vector scale and update (saxpy). The reverse routines have shown identical scaling to their forward counterparts, however some problems concerning precision need to be resolved. Further work is needed to improve the interface to realize transparent reversibility for the vector copy operation. The forward BLAS library will need to be modified to implement copy reversibility.