In practice, the overlap matrix U is usually evaluated approximated for a small subspace of the CIS states. Below, the first focus of the present paper will be the construction of an optimal algorithm for evaluating the U matrix of many electronic states with minimal cost. In particular, the first goal of the present paper is to implement an exact method for calculating the overlap matrix of singly-excited states and investigate high-lying excited-state dynamics of a molecule scattering off a metallic nanoparticle. We exploit the biorthogonal basis technique developed by Sundstrom and Head-Gordon and combine it with the protocol for choosing the phase of the adiabatic states. We find that this exact overlap calculation is actually faster by orders of magnitude than the current implementation in most state-of-the-art packages, including Q-Chem and SHARC. At this juncture, it is important to emphasize that the sign of a given eigenstate (and the sign of any column in the overlap matrix U) is undetermined. Moreover, the logarithm of the matrix U can be very sensitive to these phases of the adiabatic states and changing the signs of a column of the U matrix can lead to wildly different T matrix. To that end, if we wish to run dynamics, it is crucial to choose the phases of the states in such a way that the T matrix elements are as smooth as possible, especially when there are many electronic states and many trivial crossings. Thus, the second goal of this paper is to implement Ref. 28 to choose adiabatic eigenstates. As will be reviewed below, Ref. 28 extends parallel transport to the case of nearly trivial crossings by choosing the optimal phases of the overlap matrix through a simple optimization process.