Collections > UNC Chapel Hill Undergraduate Honors Theses Collection > Recursive Tree Algorithms for Orthogonal Matrix Generation and Matrix-Vector Multiplications in Rigid Body Simulations
pdf

In this paper, we study a numerical linear algebra problem arising from the efficient simulation of Brownian dynamics with hydrodynamics interactions where molecules are modeled as ensembles of rigid bodies. Given the first 6 rows of a matrix Q of size 3n x 3n describing how the force on each of the n particles in a rigid body P can be mapped to the 6 entries in P’s resultant force and torque, we show how the remaining 3n − 6 rows of vectors can be constructed explicitly using O(nlog(n)) operations and storage, so that (1) they form an orthonormal basis and (2) they are orthogonal to each of the first 6 vectors. For applications where only the matrix-vector multiplications are needed, without forming Q, we introduce O(n) recursive tree algorithms for computing both Q · v and QT · v for an arbitrary vector v. Preliminary numerical results are presented to demonstrate the performance and accuracy of the numerical algorithms.