Refactor and optimize ellipsoid.toPolytope

[pgagarinov]

Deadline is October 28th, by that time the changes and all the tests should be in "master" branch

ellipsoid.toPolytope method is currently based on elltool.exttbx.mpt.gen.tri2polytope function. This function uses "null" and "cross" functions which is an overkill for 2d and 3d cases. These functions should be replaced with a exact highly-efficient formulas. Once this is done one needs to write a few performance tests that make sure that toPolytope performs x% slower comparing to a performance of ellipsoid.getBoundary method (also called internally from toPolytope) where x is assumingly around 10-20%. The idea is that tri2polytope should only take a small portion of toPolytope's runtime.

The performance tests should run getBoundary and getPolytope multiple times, compare their runtimes and make sure that the difference is percentage terms is less than x where x is a constant specified in the test. The tests should be implemented in +elltool+core+test+mlunit\MPTIntegrationTestCase.m test case. The total runtime of all newly added tests should not be large though (minutes at max).

[IFShirokikh]

I replaced this functions on a exact highly-efficient formulas. Runtime of MPTIntegrationTestCase reduce about 12-17%. Now i must add new test in MPTIntegrationTestCase.m, which will check runtime of this function?

[pgagarinov]

As mentioned in the task description the test should check that getPolytope takes not more than x% to run comparing to getBoundary. x should be found empirically. You can do that by running a profiler and measuring the total runtime of getPolytope and the part of this runtime related to getBoundary. Then you write a test that calls getPolytope 10 times and calls getBoundary 10 times. For instance, if after 10 calls of getPolytope the average runtime of getPolytope is 100 seconds while he average runtime of getBoundary is 60 seconds we can conclude that getBoundary takes ~60% of the total runtime for getPolytope. Then we add a tolerance margine y% to this 60% (to remove an influence of performance fluctuations), let us say 5%. And in the test we make sure that an average runtime of getBoundary is always not more than 65%.

[pgagarinov]

1) ellShift1 - no "Vec" suffix 2) Please do not use "i", "j", "k" for counters - see Wiki 3) Prefix "S" is only for structures - see Wiki 4) In mlunitext.assert(STimeBound / STimePol < 0.28 "0.28" should be defined as constant in the beginning of the test. See Wiki for a correct naming convention for constants. In for i = 1:100 "100" should also be defined as constant. 5) All lines should be shorter than 76 symbols - use "..." to make them shorter. 6) Please use an automatic alignment tool built into Matlab. Here is how it works. You select all code via "Ctrl+A" and then press "Ctrl+I". 7) Please make sure that your code does make the code verification functionality built into Matlab editor complain (i.e. there should be a green square in the right upper corner of the editor window). I suspect that when you call "poly3 = toPolytope(ell3);" and do not use "poly3" this verificator complains. What you can do is write [~]=toPolytope(ell3). 9) Please call toPolytope and getBoundary as methods, not as if they were functions: ell3.toPolytope, ell3.getBoundary etc.

[IFShirokikh]

I fixed problems 1-7. But construction such as ell.toPolytope causes an error.

[pgagarinov]

It shouldn't case any error. Please send me the error message. For instance, on my pc ell=ellipsoid(eye(2)); poly=ell.toPolytope(); runs without any problems.

[IFShirokikh]

I found error. All problems solved.

[pgagarinov]

Ok, thanks, you can merge your task into master now. Just in case here is how to do this:

1) Switch to master 2) Merge -> from -> origin/remotes/your branch (using local branch can dangerous because it can contain unpushed changes) 3) Important !!! Set "no fast forward flag". Press OK 4) DO NOT PUSH JUST YET. Right click and open log. It should look like "petlya". 5) If eveything is ok - press push. 6) Wait for the test results for updated master. If everything ok - switch to the next task which will be assigned to your very shortly.