MSRI 2007 Parallel Computation Problem List

Specific SAGE-related Problems

1. [:msri07/threadsafety: Thread Safety of the SAGE Libraries]
2. [:msri07/pthread_sagex: Add Pthread support to SageX]
3. [:msri07/anlist: Implementation in SAGE parallel computation of elliptic curve a_p for all p up to some bound]
4. [:msri07/matrixadd: Implementation in SAGE matrix ADDITION over the rational numbers (say) using a multithreaded approach.]

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(Fp)

    • Order of the group E(Fq)

    • 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