Effective algorithms for computing triangular operator in Schubert calculus

Abstract

We develop two parallel algorithms progressively based on C++ to compute a triangle operator problem, which plays an important role in the study of Schubert calculus. We also analyse the computational complexity of each algorithm by using combinatorial quantities, such as the Catalan number, the Motzkin number, and the central binomial coefficients. The accuracy and efficiency of our algorithms have been justified by numerical experiments.

Keywords

Triangular operator / Schubert calculus / parallel algorithm / central binomial coefficient

References

[1] Bott R, Samelson H. The cohomology ring of G/T. Nat Acad Sci, 1955, 41: 490-492

[2] Donaghey R, Shapiro L W. Motzkin numbers. J Combin Theory Ser A, 1977, 23: 291-301

[3] Duan H B. Multiplicative rule of Schubert classes. Invent Math, 2005, 159(2): 407-436

[4] Duan H B. The degree of a Schubert variety. Adv Math, 2003, 180: 112-133

[5] Duan H B, Zhao X Z. Algorithm for multiplying Schubert classes. Inter J Algebra Comput, 2006, 16: 1197-1210

[6] Duan H B, Zhao X Z. A unified formula for Steenrod operations in flag manifolds. Compos Math, 2007, 143(1): 257-270

[7] Duan H B, Zhao X Z. Schubert presentation of the integral cohomology ring of the flag manifolds G/T. arXiv: 0801.2444

[8] Duan H B, Zhao X Z. The Chow rings of generalized Grassmannians. Found Comput Math, 2010, 10(3): 245-274

[9] Elizaldea S, Mansour T. Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials. Discrete Math, 2005, 305(3): 170-189

[10] Huber B, Sottile F, Sturmfels B. Numerical Schubert calculus. J Symbolic Comput, 1998, 26: 767-788

[11] Kleiman S, Laksov D. Schubert calculus. Amer Math Monthly, 1974, 79: 1061-1082

[12] Knuth D. The Art of Computer Programming, Vol 3. Sorting and Searching. Boston: Addison-Wesley, 1973, 506-542

[13] Koshy T. Catalan Numbers with Applications. Oxford: Oxford University Press, 2008

[14] Li T Y, Wang X S, Wu M N. Numerical Schubert calculus by the Pieri homotopy algorithm. SIAM J Numer Anal, 2002, 40: 578-600

[15] Pitman J. Probability. Berlin: Springer-Verlag, 1993

[16] Sottile F. Four entries for Kluwer Encyclopaedia of Mathematics. arXiv: math/0102047

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg