|
Size: 1574
Comment:
|
← Revision 18 as of 2008-11-14 13:42:04 ⇥
Size: 3615
Comment: converted to 1.6 markup
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Problem: Thread Safety = | = MSRI 2007 Parallel Computation Problem List = |
| Line 3: | 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: | Line 5: |
| 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 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/ |
MSRI 2007 Parallel Computation Problem List
Specific SAGE-related Problems
Implementation in SAGE parallel computation of elliptic curve a_p for all p up to some bound
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}
- Arithmetic of Vectors
- 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
- Generic elliptic curve operations
- 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