Differences between revisions 8 and 18 (spanning 10 versions)
⇤ ← Revision 8 as of 2007-01-22 13:11:54 →
Size: 3956
Editor: IftikharBurhanuddin
Comment:
← Revision 18 as of 2008-11-14 13:42:04 → ⇥
Size: 3615
Editor: anonymous
Comment: converted to 1.6 markup
Deletions are marked like this. Additions are marked like this.
Line 3: Line 3:
== SAGE-related Problems == == Specific SAGE-related Problems ==
Line 5: Line 5:
 * [:msri07/threadsafety: Thread Safety of the SAGE Libraries]
 * [:msri07/pthread_sagex: Add Pthread support to SageX]
 * [:msri07/anlist: Implementation in SAGE parallel computation of elliptic curve a_p for all p up to some bound]		  1. [[msri07/threadsafety| Thread Safety of the SAGE Libraries]]
 * [[msri07/pthread_sagex| Add Pthread support to SageX]]
 * [[msri07/anlist| Implementation in SAGE parallel computation of elliptic curve a_p for all p up to some bound]]
 * [[msri07/matrixadd| Implementation in SAGE matrix ADDITION over the rational numbers (say) using a multithreaded approach.]]
 * [[msri07/pointcount| Brute force count points on a variety over a finite field in parallel.]]
Line 9: Line 11:
== General Computer Algebra Problems == == 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).
Line 11: Line 15:
 {part}{I Algebra}
 {chapter}{ Arithmetic in Global Commutative Rings}
 {section}{ The ring $\@mathbb {Z}$ of Integers}
 {section}{ The ring $\@mathbb {Q}$ of Rational Numbers}
 {section}{ Arbitrary Precision Real (and Complex) Numbers}
 {section}{ Univariate Polynomial Rings}
 {section}{ Number Fields}
 {section}{ Multivariate Polynomial Rings}
 {chapter}{ Arithmetic in Local Commutative Rings}
 {section}{ Univariate Power series rings}
 {section}{ $p$-adic numbers}
 {chapter}{ Linear Algebra}
 {section}{ Arithmetic of Vectors}
 {subsection}{ Addition}
 {subsection}{ Scalar Multiplication}
 {subsection}{ Vector times Matrix}
 {section}{ Rational reconstruction of a matrix}
 {section}{ Echelon form}
 {subsection}{ Echelon form over Finite Field}
 {subsection}{ Echelon form over $\@mathbb {Q}$}
 {subsection}{ Echelon form over Cyclotomic Fields}
 {subsection}{ Echelon form (Hermite form) over $\@mathbb {Z}$}
 {section}{Kernel}
 {subsection}{ Kernel over Finite Field}
 {subsection}{ Kernel over $\@mathbb {Q}$}
 {subsection}{ Kernel over $\@mathbb {Z}$}
 {section}{ Matrix multiplication}
 {subsection}{ Matrix multiplication over Finite Fields}
 {subsection}{ Matrix multiplication over $\@mathbb {Z}$}
 {subsection}{ Matrix multiplication over Extensions of $\@mathbb {Z}$}
 {chapter}{ Noncommutative Rings}
 {chapter}{ Group Theory}
 {part}{II Arithmetic Geometry}
 {chapter}{ Groebner Basis Computation}
 {chapter}{ Elliptic Curves}
 {section}{ Generic elliptic curve operations}
 {subsection}{ Group Law}
 {subsection}{ Invariants}
 {subsection}{ Division Polynomials}
 {section}{ Elliptic curves over finite fields}
 {subsection}{ Order of the group $E({\@mathbb {F}}_{p})$}
 {subsection}{ Order of the group $E({\@mathbb {F}}_{q})$}
 {subsection}{ Order of a point}
 {section}{ Elliptic curves over ${\@mathbb {Q}}$ - part I}
 {subsection}{ Birch and Swinnerton-Dyer Conjecture}
 {subsection}{ Fourier coefficients}
 {subsection}{ Canonical height of a point}
 {subsection}{ Order of a point}
 {subsection}{ Periods}
 {subsection}{ Tate's algorithm}
 {subsection}{ Conductor and Globally minimal model}
 {subsection}{ CPS height bound}
 {subsection}{ Torsion subgroup}
 {subsubsection}{Nagell-Lutz}
 {subsubsection}{An $l$-adic algorithm}
 {subsubsection}{Another $l$-adic algorithm}
 {subsection}{ {7.3.10}Mordell-Weil via 2-descent}
 {subsection}{ {7.3.11}Saturation}
 {subsection}{ {7.3.12}Heegner points}
 {subsubsection}{Heegner discriminants}
 {subsubsection}{Heegner Hypothesis}
 {subsubsection}{Heegner point index and height}
 {section}{ Elliptic curves over ${\@mathbb {Q}}$ - part II}
 {subsection}{ Root number}
 {subsection}{ Special values of L-series}
 {subsection}{ $\# {\unhbox \voidb@x \hbox {{\fontencoding {OT2}\fontfamily {wncyr}\fontseries {m}\fontshape {n}\selectfont Sh}}}(E)$ bound}
 {subsection}{ Isogenies}
 {subsection}{ Attributes of primes}
 {subsection}{ $p$-adic height}
 {subsection}{ Modular Degree}
 {subsection}{ Modular Parameterization}
 {chapter}{ Hyperelliptic Curves}
 {chapter}{ Modular Forms}
 {section}{ Presentation of spaces of modular symbols}
 {section}{ Hecke operators on modular symbols}
 {section}{ Decomposition of spaces under the Hecke operators}
 {section}{ Trace formulas}
 {part}{III Other Topics}
 {chapter}{ Computation of tables}
 {section}{ Elliptic curves}
 {section}{ Modular forms}
 {section}{ Number fields}
 {chapter}{ Cryptography}
 {chapter}{ Coding Theory}
 {chapter}{ Constants, functions and numerical computation}		   *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/

MSRI 2007 Parallel Computation Problem List

  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/

msri07/problems (last edited 2008-11-14 13:42:04 by anonymous)