Differences between revisions 1 and 18 (spanning 17 versions)

MSRI 2007 Parallel Computation Problem List

Specific SAGE-related 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).

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

John McKay CHALLENGE system of polynomial equations

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

-  ⇤ ← Revision 1 as of 2007-01-21 03:21:51 → 
  Size: 1574
  Editor: wstein
  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 1:
-= Problem: Thread Safety =
+= MSRI 2007 Parallel Computation Problem List =
 Line 3:
-SAGE includes the C/C++ libraries listed below.  For each library, determine whether or not (or to what extent) it is thread safe.
+== Specific SAGE-related Problems ==
 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]]
 * [[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 6:
+Line 11:
-"Be careful if your application uses libraries or other objects that don't explicitly guarantee thread-safeness. When in doubt, assume that they are not thread-safe until proven otherwise.
Thread-safeness: in a nutshell, refers an application's ability to execute multiple threads simultaneously without "clobbering" shared data or creating "race" conditions. For example, suppose that you use a library routine that accesses/modifies a global structure or location in memory. If two threads both call this routine it is possible that they may try to modify this global structure/memory location at the same time. If the routine does not employ some sort of synchronization constructs to prevent data corruption, then it is not thread-safe. The implication to users of external library routines is that if you aren't 100% certain the routine is thread-safe, then you take your chances with problems that could arise." -- from [http://www.llnl.gov/computing/tutorials/pthreads/ the pthreads tutorial]
+== 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 9:
+Line 15:
+  *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
-Line 10:
+Line 98:
-== GMP: Arbitrary Precision Arithmetic Library ==
== GSL: Gnu Scientific Library ==
== MPFR: Arbitrary precision real arithmetic ==
== NTL: Number theory C++ library ==
+==  John McKay CHALLENGE system of polynomial equations ==
-Line 15:
+Line 100:
-== OpenSSL: Secure networking ==

== PARI: Number theory calculator ==

== Singular: fast commutative and noncommutative algebra ==
Singular doesn't quite have a library mode yet.  But it also includes various libraries.
+http://www.cargo.wlu.ca/McKay/

Diff for "msri07/problems"

MSRI 2007 Parallel Computation Problem List

Specific SAGE-related Problems

Parallel Implementations

John McKay CHALLENGE system of polynomial equations