Laboratory of Macromolecular Crystallography

• LMC Home page
• Library of piblications

This is a review of the works carried out in LMC of the IMPB RAS. Information on other papers in this field may be found in the original papers listed below.

Fast Differentiation Algorithm and its applications in macromolecular crystallography

(1982-2002)

       This activity started in the laboratory in early1983, after K.Kim (Central Economic - Mathematical Institute of the USSR Acad.Sci., Moscow) had announced an amazing fact in his talk at the annual conference of the Research Computing Centre. He stated that for any function ALL the components of its gradient may be calculated for the same time as is necessary to calculate ONE value of the function. To evaluate the importance of this fact for crystallography it is worthy of noting that the functions used in macromolecular crystallography may depend on hundreds of thousands variables and the calculation of one value of such a function may require minutes (or sometimes hours) of CPU work. The calculation of any particular component of the gradient (using analytical or difference formula) requires the same time as the calculation of the function value. This is a bit paradoxical that the same time is enough to calculate hundreds of thousands of components if the operations are properly grouped. This proposition was published independently by two groups, namely by Kim, Nesterov & Cherkassky and Baur & Strassen. Our work was based on the implementation scheme of the algorithm suggested by Kim et al.

      It is amazing that this unexpected algorithm is based on extremely simple rules for differentiation of a complex function ("the chain rule").

      Different aspects of the use of this idea in the practical work are the subject of the papers listed below.

Publications

The full texts of papers

Lunin, V.Yu. & Urzhumtsev, A.G. (1983). "Program construction for macromolecular atomic model refinement based on Fast Fourier and Fast Differentiation algorithms". Preprint, NCBI AN SSSR, Pushchino. (In Russian)


Lunin, V.Yu. (1984.) "The use of the fast differentiation algorithm for phase refinement". Preprint, Pushchino, NCBI AN SSSR, Russia. (In Russian)


Lunin, V.Yu. & Urzhumtsev, A.G. (1985). "Program construction for macromolecule atomic model refinement based on the fast Fourier transform and fast differentiation algorithms". Acta Cryst., A41, 327-333.


Lunin, V.Yu. (1985). "Use of the Fast Differentiation Algorithm for Phase Refinement in Protein Crystallography". Acta Cryst. A41, 551-556.


Lunin, V.Yu. (1992). "The use of statistical properties of the electron density Fourier syntheses for the solution of the phase problem in protein crystallography". Resume of Dr.Sci.Theses, ONTI PNC RAN, Pushchino, Russia. (In Russian)


Lunin, V.Yu. (1992). "The use of statistical properties of the electron density Fourier syntheses for the solution of the phase problem in protein crystallography". Dr.Sci.Theses, Institute of Crystallography RAS, Moscow, Russia. (In Russian)


Urzhumtsev, A.G. & Lunin, V.Y. (2001). "Efficient calculation of the exact matrix of the second derivatives". CCP4 Newsletter on protein crystallography, 39, 60-67.


Urzhumtsev, A.G. & Lunin, V.Y. (2001). "Fast differentiation algorithm and efficient calculation of the exact matrix of second derivatives". Acta Cryst.. A57, 451-460.