MSRI 2007 Parallel Computation Problem List

Specific SAGE-related Problems

1. Thread Safety of the SAGE Libraries

2. Add Pthread support to SageX

3. Implementation in SAGE parallel computation of elliptic curve a_p for all p up to some bound

4. Implementation in SAGE matrix ADDITION over the rational numbers (say) using a multithreaded approach.

5. Brute force count points on a variety over a finite field in parallel.

Parallel Implementations

For each of the following, make remarks about how specific practical implementable parallel algorithms could be used to enhance mathematics software libraries (e.g., SAGE).

• Arithmetic in Global Commutative Rings

  • The ring {Z} of Integers

  • The ring {Q} of Rational Numbers

  • Arbitrary Precision Real (and Complex) Numbers
  • Univariate Polynomial Rings
  • Number Fields
  • Multivariate Polynomial Rings
• Arithmetic in Local Commutative Rings
  • Univariate Power series rings

  • p-adic numbers

• Linear Algebra
  • Arithmetic of Vectors
    • Addition
    • Scalar Multiplication
    • Vector times Matrix
  • Rational reconstruction of a matrix
  • Echelon form
    • Echelon form over Finite Field

    • Echelon form over {Q}

    • Echelon form over Cyclotomic Fields

    • Echelon form (Hermite form) over {Z}

  • Kernel
    • Kernel over Finite Field

    • Kernel over {Q}

    • Kernel over {Z}

  • Matrix multiplication
    • Matrix multiplication over Finite Fields

    • Matrix multiplication over {Z}

    • Matrix multiplication over Extensions of {Z}

• Noncommutative Rings
• Group Theory
• Groebner Basis Computation
• Elliptic Curves
  • Generic elliptic curve operations
    • Group Law
    • Invariants
    • Division Polynomials
  • Elliptic curves over finite fields

    • Order of the group E({{F}}_{p})

    • Order of the group E({{F}}_{q})

    • Order of a point

  • Elliptic curves over {{Q}} - part I

    • Birch and Swinnerton-Dyer Conjecture
    • Fourier coefficients
    • Canonical height of a point
    • Order of a point
    • Periods
    • Tate's algorithm
    • Conductor and Globally minimal model
    • CPS height bound
    • Torsion subgroup
    • Nagell-Lutz

    • An l-adic algorithm

    • Another l-adic algorithm

    • Mordell-Weil via 2-descent
    • Saturation
    • Heegner points
    • Heegner discriminants
    • Heegner Hypothesis
    • Heegner point index and height

  • Elliptic curves over {{Q}} - part II

    • Root number
    • Special values of L-series
    • Sha bound
    • Isogenies
    • Attributes of primes

    • p-adic height

    • Modular Degree
    • Modular Parameterization
• Hyperelliptic Curves
• Modular Forms
  • Presentation of spaces of modular symbols
  • Hecke operators on modular symbols
  • Decomposition of spaces under the Hecke operators
  • Trace formulas
• Computation of tables
  • Elliptic curves
  • Modular forms
  • Number fields
• Cryptography
• Coding Theory
• Constants, functions and numerical computation

John McKay CHALLENGE system of polynomial equations

http://www.cargo.wlu.ca/McKay/