×

zbMATH — the first resource for mathematics

Faster geometric algorithms via dynamic determinant computation. (English) Zbl 1338.65118
Summary: The computation of determinants or their signs is the core procedure in many important geometric algorithms, such as convex hull, volume and point location. As the dimension of the computation space grows, a higher percentage of the total computation time is consumed by these computations. In this paper we study the sequences of determinants that appear in geometric algorithms. The computation of a single determinant is accelerated by using the information from the previous computations in that sequence. We propose two dynamic determinant algorithms with quadratic arithmetic complexity when employed in convex hull and volume computations, and with linear arithmetic complexity when used in point location problems. We implement the proposed algorithms and perform an extensive experimental analysis. On one hand, our analysis serves as a performance study of state-of-the-art determinant algorithms and implementations. On the other hand, we demonstrate the supremacy of our methods over state-of-the- art implementations of determinant and geometric algorithms. Our experimental results include a \(20\) and \(78\) times speed-up in volume and point location computations in dimension \(6\) and \(11\), respectively.

MSC:
65F40 Numerical computation of determinants
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Yap, C. K.; Dubé, T., The exact computation paradigm, (Du, D.-Z.; Hwang, F., Computing in Euclidean Geometry, (1995), World Scientific Singapore), 452-492, Ch. 11
[2] CGAL, Computational geometry algorithms library, (2015)
[3] Kettner, L.; Mehlhorn, K.; Pion, S.; Schirra, S.; Yap, C.-K., Classroom examples of robustness problems in geometric computations, Comput. Geom., 40, 1, 61-78, (2008) · Zbl 1135.65311
[4] Boissonnat, J.-D.; Yvinec, M., Algorithmic geometry, (1998), Cambridge University Press New York, NY, USA
[5] Seidel, R., A convex hull algorithm optimal for point sets in even dimensions, (1981), Dept. Comp. Sci., Univ. British Columbia Vancouver, Master’s thesis
[6] Büeler, B.; Enge, A.; Fukuda, K., Exact volume computation for polytopes: a practical study, (Polytopes: Combinatorics and Computation, Oberwolfach Seminars, vol. 29, (2000), Birkhäuser), 131-154 · Zbl 0960.68162
[7] Bunch, J.; Hopcroft, J., Triangular factorization and inversion by fast matrix multiplication, Math. Comput., 28, 125, 231-236, (1974) · Zbl 0276.15006
[8] Le Gall, F., Powers of tensors and fast matrix multiplication, (Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, (2014), ACM New York, NY, USA), 296-303 · Zbl 1325.65061
[9] Bareiss, E. H., Sylvester’s identity and multistep integer-preserving Gaussian elimination, Math. Comput., 22, 565-578, (1968) · Zbl 0187.09701
[10] Kaltofen, E.; Villard, G., On the complexity of computing determinants, Comput. Complex., 13, 91-130, (2005) · Zbl 1061.68185
[11] Mahajan, M.; Vinay, V., A combinatorial algorithm for the determinant, (Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’97, (1997), Society for Industrial and Applied Mathematics Philadelphia, PA, USA), 730-738 · Zbl 1321.65072
[12] Rote, G., Division-free algorithms for the determinant and the Pfaffian: algebraic and combinatorial approaches, (Alt, H., Computational Discrete Mathematics, Lecture Notes in Computer Science, vol. 2122, (2001), Springer Berlin, Heidelberg), 119-135 · Zbl 1010.65022
[13] Bird, R. S., A simple division-free algorithm for computing determinants, Inf. Process. Lett., 111, 1072-1074, (2011) · Zbl 1260.65042
[14] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, (Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, (1987), ACM New York, NY, USA), 1-6
[15] Urbańska, A., Faster combinatorial algorithms for determinant and Pfaffian, Algorithmica, 56, 35-50, (2010) · Zbl 1193.65049
[16] Krattenthaler, C., Advanced determinant calculus: a complement, Linear Algebra Appl., 411, 68, (2005) · Zbl 1079.05008
[17] Barvinok, A.; Pommersheim, J. E., An algorithmic theory of lattice points in polyhedra, (New Perspectives in Algebraic Combinatorics, vol. 38, (1999)), 91-147 · Zbl 0940.05004
[18] Rambau, J., TOPCOM: triangulations of point configurations and oriented matroids, (Cohen, A.; Gao, X.-S.; Takayama, N., Math. Software: ICMS, (2002), World Scientific), 330-340 · Zbl 1057.68150
[19] Cox, D. A.; Little, J. B.; O’Shea, D., Using algebraic geometry, Graduate Texts in Mathematics, (2005), Springer-Verlag Berlin-Heidelberg-New York
[20] Basu, S.; Pollack, R.; Roy, M.-F., Algorithms in real algebraic geometry, (2003), Springer-Verlag Berlin
[21] Emiris, I. Z.; Kalinka, T.; Konaxis, C.; Ba, T. L., Implicitization of curves and (hyper)surfaces using predicted support, Symbolic-Numerical Algorithms, Theor. Comput. Sci., 479, 81-98, (2013) · Zbl 1297.68272
[22] Dumas, J.-G.; Gautier, T.; Giesbrecht, M.; Giorgi, P.; Hovinen, B.; Kaltofen, E.; Saunders, B. D.; Turner, W. J.; Villard, G., Linbox: a generic library for exact linear algebra, (Cohen, A. M.; Gao, X.-S.; Takayama, N., First International Congress of Mathematical Software, ICMS’2002, August 2002, (2002), World Scientific Beijing, China), 40-50 · Zbl 1011.68182
[23] Guennebaud, G.; Jacob, B., Eigen v3, (2010)
[24] Clarkson, K. L., Safe and effective determinant evaluation, (Proc. 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh PA, (1992)), 387-395 · Zbl 0927.68040
[25] Brönnimann, H.; Emiris, I. Z.; Pan, V.; Pion, S., Sign determination in residue number systems, Theor. Comput. Sci., 210, 1, 173-197, (1999) · Zbl 0912.68083
[26] Abbott, J.; Bronstein, M.; Mulders, T., Fast deterministic computation of determinants of dense matrices, (Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC ’99, (1999), ACM New York, NY, USA), 197-204
[27] Brönnimann, H.; Yvinec, M., Efficient exact evaluation of signs of determinants, Algorithmica, 27, 1, 21-56, (2000) · Zbl 0947.65053
[28] Brönnimann, H.; Burnikel, C.; Pion, S., Interval arithmetic yields efficient dynamic filters for computational geometry, 14th European Workshop on Computational Geometry, Discrete Appl. Math., 109, 1-2, 25-47, (2001) · Zbl 0967.68157
[29] Kaltofen, E.; Villard, G., Computing the sign or the value of the determinant of an integer matrix, a complexity survey, J. Comput. Appl. Math., 162, 1, 133-146, (2004) · Zbl 1037.65044
[30] Emiris, I.; Fisikopoulos, V.; Konaxis, C.; Peñaranda, L., An oracle-based, output-sensitive algorithm for projections of resultant polytopes, Int. J. Comput. Geom. Appl., 23, 4-5, 397-423, (2013), (special issue of invited papers from SoCG’12) · Zbl 1297.68238
[31] Sherman, J.; Morrison, W. J., Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, Ann. Math. Stat., 21, 1, 124-127, (1950) · Zbl 0037.00901
[32] Bartlett, M. S., An inverse matrix adjustment arising in discriminant analysis, Ann. Math. Stat., 22, 1, 107-111, (1951) · Zbl 0042.38203
[33] Sankowski, P., Dynamic transitive closure via dynamic matrix inverse: extended abstract, (45th Annual IEEE Symposium on Foundations of Computer Science, 2004. Proceedings, (2004), IEEE), 509-517
[34] Avrachenkov, K.; Litvak, N., The effect of new links on google pagerank, Stoch. Models, 22, 2, 319-331, (2006) · Zbl 1094.68005
[35] Fisikopoulos, V.; Peñaranda, L., Faster geometric algorithms via dynamic determinant computation, (Proceedings of the 20th European Symposium on Algorithms, ESA 2012, Lecture Notes in Computer Science, vol. 7501, (2012), Springer Ljubljana, Slovenia), 443-454 · Zbl 1365.68439
[36] Harville, D. A., Matrix algebra from a Statistician’s perspective, (1997), Springer-Verlag New York · Zbl 0881.15001
[37] Edelsbrunner, H., Algorithms in combinatorial geometry, (1987), Springer-Verlag New York, Inc., New York, NY, USA · Zbl 0634.52001
[38] Clarkson, K. L.; Shor, P. W., Applications of random sampling in computational geometry, II, Discrete Comput. Geom., 4, 1, 387-421, (1989) · Zbl 0681.68060
[39] Garling, D. J.H., Inequalities: A journey into linear analysis, (2007), Cambridge University Press, Cambridge Books Online · Zbl 1135.26014
[40] Ziegler, G. M., Lectures on polytopes, (1995), Springer · Zbl 0823.52002
[41] (2015), Boost: peer reviewed C++ libraries
[42] Hornus, S.; Devillers, O.; Jamin, C., Dd triangulations, (CGAL User and Reference Manual, (2015)), CGAL Editorial Board
[43] J.-D. Boissonnat, O. Devillers, S. Hornus, Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension, in: SoCG, ACM, 009, pp. 208-216, http://dx.doi.org/10.1145/1542362.1542403. · Zbl 1380.68382
[44] Villard, G., A study of Coppersmith’s block wiedemann algorithm using matrix polynomials, (Apr. 1997), IMAG Research Report 975-I-M
[45] Dumas, J.-G.; Urbańska, A., An introspective algorithm for the integer determinant, (Dumas, J.-G., Transgressive Computing 2006, Copias CoCa, Madrid, Granada, Spain, (2006)), 185-202 · Zbl 1193.65047
[46] Poole, D., Linear algebra: A modern introduction, cengage learning, (2006)
[47] Berkowitz, S. J., On computing the determinant in small parallel time using a small number of processors, Inf. Process. Lett., 18, 3, 147-150, (1984) · Zbl 0541.68019
[48] Iliopoulos, C. S., Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix, SIAM J. Comput., 18, 4, 658-659, (1989) · Zbl 0689.68059
[49] Robinson, S., Toward an optimal algorithm for matrix multiplication, SIAM News, 38, 9, (2005)
[50] Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P., Numerical recipes: the art of scientific computing, (2007), Cambridge University Press · Zbl 1132.65001
[51] Clarkson, K. L.; Mehlhorn, K.; Seidel, R., Four results on randomized incremental constructions, Comput. Geom., 3, 4, 185-212, (1993) · Zbl 0781.68112
[52] Gawrilow, E.; Joswig, M., Polymake: a framework for analyzing convex polytopes, (Kalai, G.; Ziegler, G., Polytopes - Combinatorics and Computation, (2000), Birkhäuser), 43-74 · Zbl 0960.68182
[53] Fukuda, K., (2008), cddlib, version 0.94f
[54] Avis, D., Lrs: a revised implementation of the reverse search vertex enumeration algorithm, (Polytopes - Combinatorics and Computation, Oberwolfach Seminars, vol. 29, (2000), Birkhäuser-Verlag), 177-198 · Zbl 0960.68171
[55] Büeler, B.; Enge, A., Vinci
[56] Gelfand, I.; Kapranov, M.; Zelevinsky, A., Discriminants, resultants and multidimensional determinants, (1994), Birkhäuser Boston · Zbl 0827.14036
[57] Boehm, H.-J., Space efficient conservative garbage collection, (Programming Language Design and Implementation, (1993), ACM), 197-206
[58] Chand, D. R.; Kapur, S. S., An algorithm for convex polytopes, J. ACM, 17, 1, 78-86, (1970) · Zbl 0199.50902
[59] Conway, J., The book of numbers, (1996), Copernicus New York, NY
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.