ABSTRACT
Suppose A = { a 1 , , a n + 2 } â Z n has cardinality n + 2 , with all the coordinates of the a j having absolute value at most d, and the a j do not all lie in the same affine hyperplane. Suppose F = ( f 1 , , f n ) is an n × n polynomial system with generic integer coefficients at most H in absolute value, and A the union of the sets of exponent vectors of the f i . We give the first algorithm that, for any fixed n, counts exactly the number of real roots of F in time polynomial in log ( d H ) . We also discuss a number-theoretic hypothesis that would imply a further speed-up to time polynomial in n as well.
ABSTRACT
Many applications require a method for translating a large list of bond angles and bond lengths to precise atomic Cartesian coordinates. This simple but computationally consuming task occurs ubiquitously in modeling proteins, DNA, and other polymers as well as in many other fields such as robotics. To find an optimal method, algorithms can be compared by a number of operations, speed, intrinsic numerical stability, and parallelization. We discuss five established methods for growing a protein backbone by serial chain extension from bond angles and bond lengths. We introduce the Natural Extension Reference Frame (NeRF) method developed for Rosetta's chain extension subroutine, as well as an improved implementation. In comparison to traditional two-step rotations, vector algebra, or Quaternion product algorithms, the NeRF algorithm is superior for this application: it requires 47% fewer floating point operations, demonstrates the best intrinsic numerical stability, and offers prospects for parallel processor acceleration. The NeRF formalism factors the mathematical operations of chain extension into two independent terms with orthogonal subsets of the dependent variables; the apparent irreducibility of these factors hint that the minimal operation set may have been identified. Benchmarks are made on Intel Pentium and Motorola PowerPC CPUs.
