Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees | Foundations of Computational Mathematics Skip to main content
Springer Nature Link
Log in

Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees

  • Published:
Foundations of Computational Mathematics Aims and scope Submit manuscript

Abstract

Subtraction-free computational complexity is the version of arithmetic circuit complexity that allows only three operations: addition, multiplication, and division. We use cluster transformations to design efficient subtraction-free algorithms for computing Schur functions and their skew, double, and supersymmetric analogues, thereby generalizing earlier results by P. Koev. We develop such algorithms for computing generating functions of spanning trees, both directed and undirected. A comparison to the lower bound due to M. Jerrum and M. Snir shows that in subtraction-free computations, “division can be exponentially powerful.” Finally, we give a simple example where the gap between ordinary and subtraction-free complexity is exponential.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. A. Aho, J. Hopcroft, and J. Ullman, The design and analysis of computer algorithms, Addison-Wesley, 1975.

  2. A. Berenstein, S. Fomin, and A. Zelevinsky, Parametrizations of canonical bases and totally positive matrices, Adv. Math. 122 (1996), 49–149.

    Article  MathSciNet  MATH  Google Scholar 

  3. P. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, 1997.

  4. B. Bollobás, Modern graph theory, Springer, 1998.

  5. C. Chan, V. Drensky, A. Edelman, R. Kan, and P. Koev, On computing Schur functions and series thereof, preprint, 2008.

  6. W.-K. Chen, Graph theory and its engineering applications, World Scientific, 1997.

  7. V. I. Danilov, A. V. Karzanov, and G. A. Koshevoy, Systems of separated sets and their geometric models, Uspehi Mat. Nauk, 65 (2010), 67-152 (in Russian); English translation in Russian Math. Surveys 65 (2010), no. 4, 659–740.

  8. J. Demmel, M. Gu, S. Eisenstat, I. Slapničar, K. Veselić, and Z. Drmač, Computing the singular value decomposition with high relative accuracy, Linear Algebra Appl. 299 (1999), no. 1-3, 21–80.

    Article  MathSciNet  MATH  Google Scholar 

  9. J. Demmel and P. Koev, Accurate and efficient evaluation of Schur and Jack functions, Math. Comp. 75 (2006), no. 253, 223–239.

    Article  MathSciNet  MATH  Google Scholar 

  10. S. Fomin, Total positivity and cluster algebras, Proceedings of the International Congress of Mathematicians. Volume II, 125–145, Hindustan Book Agency, 2010.

  11. S. Fomin and A. Zelevinsky, Cluster algebras I: Foundations, J. Amer. Math. Soc., 15, (2002), 497–529.

    Article  MathSciNet  MATH  Google Scholar 

  12. I. Goulden and C. Greene, A new tableau representation for supersymmetric Schur functions, J. Algebra 170 (1994), 687–703.

    Article  MathSciNet  MATH  Google Scholar 

  13. D. Grigoriev, Lower bounds in algebraic complexity, J. Soviet Math. 29 (1985), 1388–1425.

    Article  Google Scholar 

  14. D. Grigoriev and N. Vorobjov, Complexity of Null- and Positivstellensatz proofs, Ann. Pure Appl. Logic 113 (2002), 153–160.

    Article  MathSciNet  MATH  Google Scholar 

  15. M. Jerrum and M. Snir, Some exact complexity results for straight-line computations over semirings, J. Assoc. Comput. Mach. 29 (1982), 874–897.

    Article  MathSciNet  MATH  Google Scholar 

  16. P. W. Kasteleyn, Graph theory and crystal physics, in: Graph theory and theoretical physics, 43–110, Academic Press, 1967.

  17. G. Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Untersuchungen der linearen Vertheilung galvanischer Ströme geführt wird, Ann. Phys. Chem. 72 (1847), 497–508.

    Article  Google Scholar 

  18. P. Koev, Accurate computations with totally nonnegative matrices, SIAM J. Matrix Anal. Appl. 29 (2007), 731–751.

    Article  MathSciNet  MATH  Google Scholar 

  19. G. L. Litvinov, Idempotent and tropical mathematics; complexity of algorithms and interval analysis. Comput. Math. Appl. 65 (2013), 1483–1496.

    Article  MathSciNet  Google Scholar 

  20. I. G. Macdonald, Schur functions: theme and variations, Séminaire Lotharingien de Combinatoire (Saint-Nabor, 1992), 5–39, Publ. Inst. Rech. Math. Av., 498, Univ. Louis Pasteur, Strasbourg, 1992.

  21. I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, 1999.

  22. A. I. Molev, Comultiplication rules for the double Schur functions and Cauchy identities, Electron. J. Combin. 16 (2009), no. 1, Research Paper 13, 44 pp.

  23. H. Narayanan, On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients, J. Algebraic Combin. 24, (2006), 347–354.

    Article  MathSciNet  MATH  Google Scholar 

  24. G. Pólya, Über positive Darstellung von Polynomen, in: Vierteljschr. Naturforsch. Ges. Zrich 73 (1928), 141–145; see: Collected Papers, vol. 2, MIT Press, Cambridge, 1974, pp. 309–313.

  25. V. Powers and B. Reznick, A new bound for Pólya’s theorem with applications to polynomials positive on polyhedra, J. Pure Appl. Algebra 164 (2001), 221–229.

    Article  MathSciNet  MATH  Google Scholar 

  26. J. Riordan, Review MR0022160 (9,166f), Math. Reviews, AMS, 1948.

  27. G. Rote, Division-free algorithms for the determinant and the Pfaffian: algebraic and combinatorial approaches. Computational discrete mathematics, 119–135, Lecture Notes in Comput. Sci. 2122, Springer, Berlin, 2001.

  28. C. P. Schnorr, A lower bound on the number of additions in monotone computations, Theor. Comput. Sci. 2, (1976), 305–315.

    Article  MathSciNet  MATH  Google Scholar 

  29. E. Shamir and M. Snir, Lower bounds on the number of multiplications and the number of additions in monotone computations, Technical Report RC-6757, IBM, 1977.

  30. A. Shpilka and A. Yehudayoff, Arithmetic circuits: a survey of recent results and open questions, Found. Trends Theor. Comput. Sci. 5 (2009), no. 3–4, 207–388 (2010).

  31. R. P. Stanley, Enumerative combinatorics, vol. 2, Cambridge University Press, 1999.

  32. V. Strassen, Vermeidung von Divisionen, J. Reine Angew. Math. 264 (1973), 184–202.

    MathSciNet  MATH  Google Scholar 

  33. W. T. Tutte, Graph theory, Addison-Wesley, 1984.

  34. W. T. Tutte, Graph theory as I have known it, Oxford University Press, 1998.

  35. L. G. Valiant, Negation can be exponentially powerful, Theor. Comput. Sci. 12, (1980), 303–314.

    Article  MathSciNet  MATH  Google Scholar 

  36. D. G. Wagner, Matroid inequalities from electrical network theory, Electron. J. Combin. 11 (2004/06), no. 2, Article 1, 17 pp.

Download references

Acknowledgments

We thank Leslie Valiant for bringing the paper [15] to our attention.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Michigan, 530 Church Street, Ann Arbor, MI, 48109-1043, USA

    Sergey Fomin

  2. CNRS, Mathématiques, Université de Lille, 59655, Villeneuve d’Ascq, France

    Dima Grigoriev

  3. Central Institute of Economics and Mathematics, Nahimovskii pr. 47, 117418, Moscow, Russia

    Gleb Koshevoy

Authors
  1. Sergey Fomin
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Dima Grigoriev
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Gleb Koshevoy
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Sergey Fomin.

Additional information

Communicated by Peter Bürgisser.

We thank the Max-Planck Institut für Mathematik for its hospitality during the writing of this paper. Partially supported by NSF Grant DMS-1101152 (S. F.), RFBR/CNRS Grant 10-01-9311-CNRSL-a, and MPIM (G. K.).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fomin, S., Grigoriev, D. & Koshevoy, G. Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees. Found Comput Math 16, 1–31 (2016). https://doi.org/10.1007/s10208-014-9231-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10208-014-9231-y

Keywords

Mathematics Subject Classification