Quadratic Zonotopes
Assalé Adjé, Pierre-Loïc Garoche and Alexis Werey
1 Paper
- submission.pdf
- script to generate experiments parts of the paper: run benchmark
2 Prototype
- implemented in Ocaml
- GPL v3.
- dependencies:
- OSDP package as well as CSDP or Mosek SDP solvers
- apron analysis library. Either the svn latest version or ubuntu package (you may have to change the lflags in src/Makefile)
- the (sound) interval library of JM Alliot: http://www.alliot.fr/fbbdet.html.fr (works only on Intel processors) this library is provided in the tar.
- source of the prototype tiny-0.2.tgz
- source of OSDP osdp-0.2.tgz
3 Experiments
- source of experiments: experiments.tgz
3.1 Results
| Name | Interval | (ms) | Affine Zonotopes | (ms) | Quadratic Zonotopes | (ms) | Apron T1P | (ms) |
| atan | [-1.9191498112, 1.9191498112] | 7 | [-1.9191498112, 1.9191498112] | 11 | best{[-1.0028662257, 1.0028662257]} | 3 | [-1.3494077616, 1.34940776161] | 13 |
| atan10 | [-1.9191498112, 1.9191498112] | 0 | [-2.3648467673, 2.3648467673] | 6 | [-1.5975015122, 1.5917690608] | 8 | best{[-1.47753577898, 1.47753577899]} | 8 |
| stolfi1 | [0., infty] | 0 | [-infty, +infty] | 0 | [-0.850616332819, 3.25431718313] | 5 | best{[0., 3.60555127547]} | 6 |
| stolfi2 | [0., 3.60555127546] | 7 | [-infty, +infty] | 3 | [-infty, +infty] | 6 | best{[-0., 2.511913348]} | 5 |
| stolfi3 | [0., 5.38515366544] | 6 | [-2.9813971375, 10.816826897] | 3 | [-0.627587100169, 3.24719752499] | 4 | best{[-0., 1.75167279806]} | 6 |
| stolfi4 | [0., 2.2360679775] | 11 | [-infty, +infty] | 8 | [-0.333608410107, 3.26436860979] | 0 | best{[0.356871387229, 1.71844365727]} | 8 |
| stolfi5 | [0., 2.18118677732] | 0 | [-0.428837825689, 3.03896267132] | 4 | [0.0874449137755, 2.38574456857] | 4 | best{[0.347789103496, 1.55341272544]} | 7 |
| stolfi6 | [0., 2.18817574984] | 3 | [-0.714719855364, 2.91547506239] | 9 | [0.116932060593, 2.30853714787] | 11 | best{[0.389299767788, 1.65996960294]} | 8 |
| stolfi7 | [0., 1.89644276761] | 6 | [0.190189454163, 2.2360691228] | 3 | [0.294006000069, 1.97529607732] | 6 | best{[0.451242455713, 1.46266465828]} | 8 |
| stolfi8 | [-0., 1.82574185835] | 4 | [0.209405904142, 2.] | 0 | [0.299095720095, 1.88866952202] | 3 | best{[0.478600298372, 1.40829099394]} | 3 |
| stolfi9 | [0., 1.73582044704] | 10 | [0.261122645746, 1.89085560702] | 6 | [0.33670287078, 1.7563765154] | 10 | best{[0.474977015706, 1.40732357365]} | 7 |
| stolfi10 | [0., 1.71446607998] | 11 | [0.321714045973, 1.82888698016] | 0 | [0.360747604569, 1.75355405678] | 5 | best{[0.493635289045, 1.38248961788]} | 0 |
| stolfi11 | [0., 1.6742485743] | 3 | [0.342084688833, 1.74828402093] | 3 | [0.395910595842, 1.67780367926] | 4 | best{[0.511907954995, 1.36610568602]} | 15 |
| stolfi13 | [0., 1.61553612293] | 10 | [0.382989435656, 1.67199107058] | 0 | [0.414111611946, 1.61916877888] | 8 | best{[0.511801629482, 1.35084157251]} | 6 |
| stolfi30 | [0.353137235758, 1.43321935142] | 10 | [0.482522078874, 1.44130559408] | 13 | [0.488619837303, 1.43294342567] | 16 | best{[0.536033844071, 1.31442087716]} | 11 |
| stolfi40 | [0.402015126104, 1.40182605164] | 11 | [0.498251943728, 1.40591898313] | 15 | [0.501705890284, 1.40125302172] | 14 | best{[0.537788981372, 1.31099749155]} | 15 |
| stolfi50 | [0.431479305647, 1.3824506302] | 12 | [0.507757089721, 1.38488881663] | 24 | [0.509966897923, 1.38193351703] | 26 | best{[0.53914628643, 1.30927077152]} | 18 |
| stolfi55 | [0.442346844186, 1.3751858494] | 14 | [0.511030377071, 1.37725187044] | 28 | [0.512947338464, 1.37471896856] | 27 | best{[0.539548641259, 1.30881584043]} | 19 |
| stolfi100 | [0.487873369016, 1.34399313223] | 27 | [0.525265694578, 1.34455208136] | 69 | [0.525833805055, 1.34381694756] | 52 | best{[0.540769952028, 1.30718524721]} | 30 |
| stolfi200 | [0.514830559554, 1.32515153857] | 40 | [0.53338907106, 1.32528925242] | 272 | [0.53353521556, 1.32510440665] | 209 | best{[0.541094613181, 1.30671642174]} | 48 |
| stolfi300 | [0.523655900004, 1.31893839325] | 50 | [0.536011673982, 1.31899817244] | 710 | [0.536076440613, 1.31891668] | 439 | best{[0.541136804839, 1.30663632943]} | 90 |
| stolfi400 | [0.52806882845, 1.31583210989] | 67 | [0.53732865473, 1.31586533923] | 1359 | [0.537365034365, 1.31581960463] | 842 | best{[0.541168274883, 1.30660176012]} | 111 |
| Ln1px | [-0.00787353515625, 0.46641031901] | 4 | [-0.000518798828125, 0.4074122111] | 8 | best{[-0.000208536783855, 0.403292338053]} | 5 | [-5.14984130859e-05, 0.404132843018] | 3 |
| householderorig | best{[0.111227035522, 0.112396240234]} | 5 | [0.1112241745, 0.112396240234] | 7 | [0.111225605011, 0.112396240234] | 0 | [0.111227035523, 0.112396240235] | 2 |
| householderorig | [0.176085267318, 0.18458429974] | 0 | [0.176566574488, 0.184067129249] | 8 | [0.176635430244, 0.184066579531] | 0 | best{[0.176673007421, 0.184067107048]} | 7 |
| householderorig | [0.210834740618, 0.248666692327] | 4 | [0.217988978669, 0.240692923792] | 7 | [0.218629392179, 0.240664851438] | 0 | best{[0.218853931983, 0.240685956492]} | 9 |
| householderorig | [0.175030643971, 0.292348049011] | 6 | [0.221261465409, 0.250120354148] | 6 | best{[0.222568163151, 0.249902358391]} | 11 | [0.222457871102, 0.250015406454] | 3 |
| householderorig | [0.0316950557142, 0.422034948802] | 0 | [0.221104854098, 0.250299666692] | 10 | best{[0.222567999936, 0.249935388853]} | 3 | [0.222412630174, 0.250090406047] | 3 |
| householderorig | [-0.907983583359, 1.66869396242] | 7 | [0.221066484209, 0.250338036582] | 12 | best{[0.222569468721, 0.249942479832]} | 5 | [0.222405987966, 0.25009707694] | 0 |
| householderorig | [-1117.82949059, 1899.48675547] | 11 | [0.221056907974, 0.250347612817] | 26 | best{[0.222574741444, 0.24995439556]} | 7 | [0.222404998031, 0.250098070222] | 3 |
| householderorig | [-2.18278981511e+18, 3.7091346565e+18] | 3 | [0.221054510582, 0.250350010209] | 16 | best{[0.222587681064, 0.24997597693]} | 3 | [0.222404849877, 0.250098218875] | 14 |
| householderorig | [-6.19717241056e+94, 1.05306277321e+95] | 4 | [0.221053909938, 0.250350610853] | 32 | best{[0.222616032941, 0.250016979308]} | 12 | [0.222404827701, 0.250098241125] | 11 |
| householderorig | [-infty, infty] | 4 | [0.221053759423, 0.250350761368] | 39 | best{[0.222675392935, 0.250097047667]} | 7 | [0.222404824382, 0.250098244456] | 4 |
| householderorig | [-infty, infty] | 8 | [0.221053721704, 0.250350799087] | 34 | best{[0.222797256763, 0.250255861785]} | 6 | [0.222404823885, 0.250098244955] | 7 |
| householderorig | [-infty, infty] | 7 | [0.221053712252, 0.250350808539] | 37 | best{[0.22304560616, 0.250574053469]} | 4 | [0.22240482381, 0.250098245029] | 8 |
| householderorig | [-infty, infty] | 11 | [0.221053709883, 0.250350810908] | 20 | best{[0.223551959863, 0.251217461206]} | 7 | [0.222404823799, 0.25009824504] | 3 |
| householderorig | [-infty, infty] | 0 | [0.221053709289, 0.250350811502] | 22 | [0.224593105002, 0.252535484362] | 6 | best{[0.222404823798, 0.250098245042]} | 7 |
| householderorig | [-infty, infty] | 3 | [0.22105370914, 0.250350811651] | 11 | [0.226779407834, 0.255300296556] | 7 | best{[0.222404823797, 0.250098245042]} | 10 |
| householderorig | [-infty, infty] | 4 | [0.221053709103, 0.250350811688] | 21 | [0.231586420269, 0.261386894149] | 3 | best{[0.222404823797, 0.250098245042]} | 9 |
| householderorig | [-infty, infty] | 7 | [0.221053709094, 0.250350811697] | 21 | [0.243284071423, 0.276271987424] | 6 | best{[0.222404823797, 0.250098245042]} | 11 |
| householder | best{[0.111227035522, 0.112396240234]} | 7 | [0.1112241745, 0.112396240234] | 2 | [0.111225605011, 0.112396240234] | 4 | [0.111227035523, 0.112396240235] | 7 |
| householder | [0.176085267318, 0.18458429974] | 5 | [0.1765520415, 0.184081662238] | 10 | best{[0.176592448768, 0.184067082078]} | 10 | [0.176581570978, 0.184079390938] | 3 |
| householder | [0.210834740618, 0.248666692327] | 4 | [0.217305331674, 0.241376570787] | 7 | best{[0.218183266697, 0.240745015184]} | 5 | [0.217634286882, 0.241294242073] | 3 |
| householder | [0.175030643971, 0.292348049011] | 0 | [0.215133303347, 0.25624851621] | 6 | best{[0.221258481678, 0.251013063048]} | 11 | [0.216838613447, 0.255438994291] | 5 |
| householder | [0.0316950557142, 0.422034948802] | 4 | [0.206669773298, 0.264734747492] | 12 | best{[0.219857523718, 0.252700077655]} | 20 | [0.210526081422, 0.262044644179] | 11 |
| householder | [-0.907983583359, 1.66869396242] | 6 | [0.195545565371, 0.27585895542] | 4 | best{[0.218226660805, 0.254439146789]} | 16 | [0.203346811741, 0.269299010302] | 12 |
| householder | [-1117.82949059, 1899.48675547] | 0 | [0.175681120064, 0.295723400727] | 11 | best{[0.216346068332, 0.256539206877]} | 13 | [0.193621912437, 0.279150970617] | 4 |
| householder | [-2.18278981511e+18, 3.7091346565e+18] | 3 | [0.122747435567, 0.348657085224] | 10 | best{[0.214090879758, 0.259242477059]} | 9 | [0.177291928719, 0.29576822668] | 7 |
| householder | [-6.19717241056e+94, 1.05306277321e+95] | 3 | [-0.168673506326, 0.640078027117] | 6 | best{[0.211215020339, 0.263037078346]} | 16 | [0.140567915967, 0.333423898376] | 10 |
| householder | [-infty, infty] | 3 | [-14.0846606002, 14.556065121] | 8 | best{[0.207187244597, 0.268965153777]} | 15 | [0.00503619815383, 0.474972172161] | 9 |
| householder | [-infty, infty] | 0 | [-98003775.3617, 98003775.8331] | 11 | best{[0.20074542331, 0.279409110013]} | 22 | [-1.45428750424, 2.24238756084] | 9 |
| householder | [-infty, infty] | 7 | [-1.35614241845e+42, 1.35614241845e+42] | 11 | best{[0.188425036491, 0.300484562298]} | 16 | [-5335.40355333, 8226.73819663] | 10 |
| householder | [-infty, infty] | 4 | [-6.88046453919e+212, 6.88046453919e+212] | 9 | best{[0.158030883483, 0.351685620227]} | 11 | [-3.6658039829e+21, 5.65235775441e+21] | 5 |
| householder | [-infty, infty] | 3 | [-infty, +infty] | 13 | best{[0.0404184705961, 0.529372266662]} | 11 | [-5.612793509e+110, 8.65444990033e+110] | 7 |
| householder | [-infty, infty] | 5 | [-infty, +infty] | 7 | best{[-1.4128134184, 2.27861393355]} | 11 | [-infty, infty] | 6 |
| householder | [-infty, infty] | 5 | [-infty, +infty] | 10 | best{[-2570.28287632, 2582.02038977]} | 11 | [-infty, infty] | 16 |
| householder | [-infty, infty] | 0 | [-infty, +infty] | 10 | best{[-2.85558172102e+18, 2.85558172104e+18]} | 7 | [-infty, infty] | 6 |
| householder | [-infty, infty] | 5 | [-infty, +infty] | 17 | best{[-4.62025982136e+93, 4.62025982136e+93]} | 18 | [-infty, infty] | 11 |
| controller | [-0.218215767945, 0.218215767945] | 7 | best{[-0.15333723884, 0.15333723884]} | 53 | best{[-0.15333723884, 0.15333723884]} | 21 | best{[-0.153337238839, 0.15333723884]} | 10 |
| controller | [-0.427244657381, 0.427244657381] | 12 | best{[-0.19838937052, 0.19838937052]} | 191 | best{[-0.19838937052, 0.19838937052]} | 20 | best{[-0.198389370519, 0.19838937052]} | 18 |
| controller | [-0.658610187104, 0.658610187104] | 20 | best{[-0.204684651748, 0.204684651748]} | 518 | best{[-0.204684651748, 0.204684651748]} | 49 | best{[-0.204684651747, 0.204684651748]} | 21 |
| controller | [-1.25775315682, 1.25775315682] | 30 | best{[-0.235586257434, 0.235586257434]} | 1865 | best{[-0.235586257434, 0.235586257434]} | 74 | [-0.235586257433, 0.235586257434] | 35 |
| SinCos | [0.866211267344, 1.1826645311] | 8 | [0.999998001209, 1.01245331268] | 10 | [0.999656374047, 1.00653098567] | 7 | best{[0.99999800121, 1.00618859531]} | 2 |
Results were obtained with the same call to the tool as in the paper but without the truncation: cat results.tex | sed "s/&/|/g"| xargs | sed "s/\\\\/|\n/g" | grep -v "^$" | sed "s/^/|/g"