Flexibility of Cyclo-Octane Using Resultants of Polynomial Systems
Last modified: 2010-05-30
Abstract
\documentstyle{llncs}
\linespread{1.4}
\setlength{\textwidth}{13.6cm}
\setlength{\evensidemargin}{14mm}
\setlength{\oddsidemargin}{14mm}
\setlength{\headheight}{-1mm}
\pagestyle{plain}
\pagenumbering{arabic}
\begin{document}
\begin{large}
\begin{frontmatter}
\title{Flexibility of Cyclo-Octane Using Resultants of Polynomial Systems }
\author{\Large Robert H. Lewis\inst{1} }
\institute{Fordham University, New York, NY 10458, USA}
\maketitle
\end{frontmatter}
We solve systems of multivariate polynomial equations in order to
understand flexibility of three
dimensional objects, including molecules.
Protein flexibility is a major research topic in
computational
chemistry. In general, a polypeptide backbone can be modeled as
a polygonal line whose edges and angles are fixed while some of the
dihedral angles can vary freely.
It is well known that a segment of backbone with
fixed ends will be (generically) flexible if it includes
more than six free torsions. Resultant methods have been applied successfuly to this
problem, see \cite{cout1}, \cite{cout2}.
In this work we focus on non-generically flexible structures (like a geodesic dome)
that are rigid but become
continuously movable under certain relations. The subject has a long history:
Cauchy (1812), Bricard (1896), Connelly (1978).
In our previous work \cite{LC}, we began
a new approach to understanding flexibility, using not numeric but symbolic computation.
We describe the geometry of the object with a set of
multivariate polynomial equations, which we solve with resultants. Resultants were pioneered by
Bezout, Sylvester, Dixon,
and others. The resultant appears as a factor of the
determinant of a matrix containing multivariate
polynomials. Given the resultant, we described
\cite{LC} an algorithm $Solve$
that examines it and determines relations for the structure to be
flexible.
We discovered in this way the conditions of flexibility
for an arrangement of quadrilaterals in Bricard \cite{bric}, which models molecules.
Here we significantly extend the algorithm and the molecular structures.
\subsection{ \bf Cyclo-Octane Molecule}
Next we consider the cylo-octane molecule, pictured in figure 1.
Chemically relevant solutions fix the (bond) angles between the paler lines,
introducing four constraint equations in the variables $\tau_i$.
To save space, we show one equation here; the other three are similar.
\vspace*{1mm}
\begin{figure}
\vspace{7.4cm}
{\hskip 17mm \special{illustration octane.epsf scaled 250} }
\vspace{ -13mm}
\caption {\large Geometry of Octane Molecule. }
\end{figure}
\vspace{2mm}
\noindent
$ - {t\beta}^4\, {\tau_4}^2\, {\tau_1}^2 - 4\, {t\alpha_1}\, {t\beta}^3\,
{\tau_4}^2\, {\tau_1}^2 + 6\, {t\beta}^2\, {\tau_4}^2\, {\tau_1}^2 + 4\,
{t\alpha_1}\, {t\beta}\,
{\tau_4}^2\, {\tau_1}^2 - {\tau_4}^2\, {\tau_1}^2 - {t\beta}^4\, {\tau_1}^2
+ 4\, {t\alpha_1}^2\, {t\beta}^2\, {\tau_1}^2 + 2\, {t\beta}^2\, {\tau_1}^2
- {\tau_1}^2 - 8\,
{t\alpha_1}^2\, {t\beta}^2\, {\tau_4}\, {\tau_1} - 8\, {t\beta}^2\,
{\tau_4}\, {\tau_1} - {t\beta}^4\, {\tau_4}^2 + 4\, {t\alpha_1}^2\,
{t\beta}^2\, {\tau_4}^2 + 2\,
{t\beta}^2\, {\tau_4}^2 - {\tau_4}^2 - {t\beta}^4 + 4\, {t\alpha_1}\,
{t\beta}^3 + 6\, {t\beta}^2 - 4\, {t\alpha_1}\, {t\beta} - 1 = 0$
\vspace{1mm}
\noindent
Here $\tau_i = \tan(z_i/2)$, $t\beta = \tan(\beta/2)$, and $t\alpha_i =
\tan(\alpha_i/2)$.
We use the Dixon resultant to eliminate $\tau_2, \tau_3$, and $\tau_4$. An
important {\bf special case} is when the basic
quadrilateral (heavy black lines) is planar. The equations then simplify quite
a bit, and we can describe all the solutions of this
case.
The Dixon matrix is $24 \times 24$. 57\% of the entries are 0. On average there are 41 terms per entry. The Dixon-EDF method \cite{lh} takes 3 minutes 38 seconds to compute the resultant for $\tau_1$, which has 21715 terms. It is degree 32 in $\tau_1$ but has only even degree terms.
In the {\bf general case} (three dimensional space) we have now computed the entire resultant over ground ring Z = the integers. The Dixon matrix is $64 \times 64$. 64\% of the entries are 0. On average there are 107 terms per entry.
The
determinant of the Dixon matrix here, were it ever computed, would have
many billions of terms. Two years ago, working over ground ring a finite field, our Dixon-EDF techniques \cite{lh} discovered its hundreds
of factors in about 65 hours of CPU time. The largest has 4872161 terms. However, we want the answer over Z to detect flexibility.
Recently, we have reduced this time to 13 hours by using new heuristics in the EDF algotithm. Furthermore, using new ideas including an efficient LaGrange interpolation algorithm, we have now computed the entire resultant over ground ring Z in 396 hours, 16.5 days. We seem to have found new interesting flexible cases. Work is ongoing.
%
% ---- Bibliography ----
%
\begin{thebibliography}{15}
\bibitem {bric}
Bricard, Raoul,
M\'emoire sur la th\'eorie de l'octa\`edre articul\'e,
J. Math. Pures Appl. 3 (1897), p. 113 - 150 \\
(English translation: http://www.math.unm.edu/$\sim$vageli/papers/bricard.pdf).
\bibitem {cauch}
Cauchy, A.\ L. Sur les polygones et les polyhedres. Second Memoire. Journal
de l'\'Ecole Polytechn. {\bf 9} (1813), pp. 8.
\bibitem {cout1}
Coutsias, E.\ A., C.\ Seok, M.\ P. Jacobson and K.\ A. Dill
A Kinematic View of Loop Closure,
J. Comput. Chem., 25 (2004), no. (4), p. 510 - 528.
\bibitem {cout2}
Coutsias, E.\ A., C. Seok, M.\ J. Wester and K.\ A. Dill, Resultants and loop
closure,
Int. J. Quantum Chem. 106 (2005), no. (1), p. 176 -
189.
\bibitem {stef}
Cromwell, P.\ R. {\it Polyhedra}. New York: Cambridge Univ. Press, 1997. p.
222 - 224.
\bibitem{cox} Cox, D., J. Little, D. O'Shea. Using Algebraic Geometry.
Graduate Texts in Mathematics, 185. Springer-Verlag.
New York, 1998.
\bibitem {dix}
Dixon, A.\ L. The eliminant of three quantics in two independent variables.
Proc. London Math. Soc., {\bf 6} (1908) p. 468 - 478.
\bibitem {LC}
Lewis, R.\ H. and E.\ A. Coutsias, Algorithmic Search for Flexibility
Using Resultants of Polynomial Systems; in
Automated Deduction in Geometry, 6th International Workshop, ADG 2006.
Springer-Verlag. LNCS {\bf 4869} p. 68 - 79 (2007).
\bibitem{lh} Lewis, R.\ H., Heuristics to accelerate the Dixon
resultant. Mathematics and Computers in Simulation {\bf 77}, Issue 4, p.
400-407, April 2008.
\bibitem{lm} Lewis, R.\ H., Flexible structures movie, http://home.bway.net/lewis/flex2.MOV. December 2008.
\bibitem {thor}
Thorpe, M., M. Lei, A.\ J. Rader, D.\ J. Jacobs, L. Kuhn. Protein flexibility
and dynamics using constraint theory.
J. Molecular Graphics and Modelling {\bf 19} (2001) p. 60 - 69.
\end{thebibliography}
%
\end{document}