Editing Verlet integration (section)

==Constraints==
{{Main article|Constraint algorithm}}
Systems of multiple particles with constraints are simpler to solve with Verlet integration than with Euler methods.  Constraints between points may be, for example, potentials constraining them to a specific distance or attractive forces.  They may be modeled as [[spring (device)|springs]] connecting the particles.  Using springs of infinite stiffness, the model may then be solved with a Verlet algorithm.

In one dimension, the relationship between the unconstrained positions <math>\tilde{x}_i^{(t)}</math> and the actual positions <math>x_i^{(t)}</math> of points <math>i</math> at time <math>t</math>, given a desired constraint distance of <math>r</math>, can be found with the algorithm

:<math>\begin{align}
d_1 &= x_2^{(t)} - x_1^{(t)}, \\[6px]
d_2 &= \|d_1\|, \\[6px]
d_3 &= \frac{d_2 - r}{d_2}, \\[6px]
x_1^{(t + \Delta t)} &= \tilde{x}_1^{(t + \Delta t)} + \tfrac{1}{2} d_1 d_3, \\[6px]
x_2^{(t + \Delta t)} &= \tilde{x}_2^{(t + \Delta t)} - \tfrac{1}{2} d_1 d_3.
\end{align}</math>

Verlet integration is useful because it directly relates the force to the position, rather than solving the problem using velocities.

Problems, however, arise when multiple constraining forces act on each particle. One way to solve this is to loop through every point in a simulation, so that at every point the constraint relaxation of the last is already used to speed up the spread of the information. In a simulation this may be implemented by using small time steps for the simulation, using a fixed number of constraint-solving steps per time step, or solving constraints until they are met by a specific deviation.

When approximating the constraints locally to first order, this is the same as the [[Gauss–Seidel method]]. For small [[Matrix (mathematics)|matrices]] it is known that [[LU decomposition]] is faster. Large systems can be divided into clusters (for example, each [[ragdoll physics|ragdoll]]&nbsp;=&nbsp;cluster). Inside clusters the LU method is used, between clusters the [[Gauss–Seidel method]] is used. The matrix code can be reused: The dependency of the forces on the positions can be approximated locally to first order, and the Verlet integration can be made more implicit.

Sophisticated software, such as SuperLU<ref>[http://crd.lbl.gov/~xiaoye/SuperLU/superlu_ug.pdf SuperLU User's Guide].</ref> exists to solve complex problems using sparse matrices.  Specific techniques, such as using (clusters of) matrices, may be used to address the specific problem, such as that of force propagating through a sheet of cloth without forming a [[sound wave]].<ref>{{cite journal|last1=Baraff|first1=D.|last2=Witkin|first2=A.|title=Large Steps in Cloth Simulation|journal=Computer Graphics Proceedings|date=1998|volume=Annual Conference Series|pages=43–54|url=https://www.cs.cmu.edu/~baraff/papers/sig98.pdf}}</ref>

Another way to solve [[holonomic constraints]] is to use [[constraint algorithm]]s.