Distributed Landmarking: Spring Network in Equilibrium
After two days of search for a material on analysis spring network, I came across a paper from Fluid mechanics.
Frederic. J. Blom, "Considerations on Spring Analogy", International Journal for Numerical Methods in Fluids, Vol. 32, pp. 647-668, 2000.
One of my previous major struggle is to find the equilibrium condition in a spring network. From this paper, I found out that the condition is "the resultant force in every node is zero"! It's embarrassing how I didn't think about it (or actually forgot it)!!.
The major idea I got from this paper is that a spring network can be modeled as linear simultaneous equations (variables are the displacement vectors). Once modeled as simultaneous equations, we can use iterative methods to solve this system. Iterative methods are preferred here as they can be easily fit as a distributed algorithm.
The thing that puzzles me is why no body approach this as linear simultaneous equations. Everybody tried optimization approaches to minimize the stress between nodes or the energy in the system. Solving the linear simultaneous equations provides the same results: minimize the stress/energy.
Jacobi method is one way of solving the linear simultaneous equations iteratively. Actually, Vivaldi's Spring algorithm is very close to this Jacobi iteration, even though Vivaldi does not recognize this so. Jacobi iteration still needs O(I*n^2) messages, where I is the number of iterations. Fortunately there are some fast iterative methods such as accelerated Gauss-Seidel method to reduce I. The advantage is much reduced computational complexity; there is no complex optimization procedure, but just multiplications and additions.
Frederic. J. Blom, "Considerations on Spring Analogy", International Journal for Numerical Methods in Fluids, Vol. 32, pp. 647-668, 2000.
One of my previous major struggle is to find the equilibrium condition in a spring network. From this paper, I found out that the condition is "the resultant force in every node is zero"! It's embarrassing how I didn't think about it (or actually forgot it)!!.
The major idea I got from this paper is that a spring network can be modeled as linear simultaneous equations (variables are the displacement vectors). Once modeled as simultaneous equations, we can use iterative methods to solve this system. Iterative methods are preferred here as they can be easily fit as a distributed algorithm.
The thing that puzzles me is why no body approach this as linear simultaneous equations. Everybody tried optimization approaches to minimize the stress between nodes or the energy in the system. Solving the linear simultaneous equations provides the same results: minimize the stress/energy.
Jacobi method is one way of solving the linear simultaneous equations iteratively. Actually, Vivaldi's Spring algorithm is very close to this Jacobi iteration, even though Vivaldi does not recognize this so. Jacobi iteration still needs O(I*n^2) messages, where I is the number of iterations. Fortunately there are some fast iterative methods such as accelerated Gauss-Seidel method to reduce I. The advantage is much reduced computational complexity; there is no complex optimization procedure, but just multiplications and additions.
posted by Unknown at
1:41 AM
0 Comments:
Post a Comment
<< Home