Martin Rohde wrote:
I'm using the library now for calculating the intersection of two convex polyhedra. During my calculations, a large number of intersections must be calculated (say 50000 times). The library does its calculations very well, but it costs a lot of time to calculate an intersection. In my code I do the following:
- Add generators to a polyhedron 1
- Add generators to a polyhedron 2
- Calculate the intersection of polyhedra 1 and 2
- Store the constraints and the generators in an array (I convert all
coefficients to doubles)
This process costs 100 seconds for 30000 calculations (so 30 intersections per second) on a 600MHz machine.
When I remove step 3 (so I skip the intersection), the calculation takes about the same amount of time. So, the intersection is not the time consuming step. But removing step 1 and/or 2 speeds up the calculation significantly! So I might conclude that the ph.add_generator(ax+by+cz) is very slow.
My questions are now:
- is add_generator slow indeed?
- How can I speed up the code?
Dear Martin,
I assume you are creating polyhedra p1 and p2 empty. That is, with some code like (feel free to substitute `C_Polyhedron' with `NNC_Polyhedron')
C_Polyhedron p1(n, C_Polyhedron::EMPTY); C_Polyhedron p2(n, C_Polyhedron::EMPTY);
In this case, the computational cost of each call to `add_generator' you are performing is amortized linear in `n' (the space dimension of the polyhedron involved).
The cost of obtaining the constraints of the polyhedra starting from the generators is, in the worst case, exponential. Since intersection is computed by performing the union of the constraints for polyhedra p1 and p2, your step 3 has also exponential complexity (since first it computes the constraints for both p1 and p2). Notice also that, if you omit step 3, you will pay an exponential price in step 4 since, in order to store the constraints in the array you must first compute the constraints. On the other hand, if step 3 is not omitted, step 4 will be (relatively) very cheap since the constraints have already been computed.
So the answer to the question "is add_generator slow?" is "no". In order to answer the question "how can I speed up the code?" we would need to either see your code or to know (much) more about your application. For instance, what is the range of dimensions you are using for your polyhedra? What is the order of magnitude of the number of generators you are injecting into the polyhedra? Are you using C_Polyhedron or NNC_Polyhedron? Did you compile the library by yourself? If so, which options did you give to configure? An answer to these questions may put us on the right track, but seeing the code would perhaps also allow us to improve the library. All the best
Roberto