Differences between revisions 1 and 9 (spanning 8 versions)
Revision 1 as of 2007-01-21 03:21:51
Size: 1574
Editor: wstein
Comment:
Revision 9 as of 2007-01-22 13:12:47
Size: 3970
Comment:
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. == 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]
Line 6: Line 9:
"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]
== General Computer Algebra Problems ==
Line 9: Line 11:
{{{
Line 10: Line 13:
== GMP: Arbitrary Precision Arithmetic Library ==
== GSL: Gnu Scientific Library ==
== MPFR: Arbitrary precision real arithmetic ==
== NTL: Number theory C++ library ==
 {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}
Line 15: Line 99:
== 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.
}}}

MSRI 2007 Parallel Computation Problem List

  • [: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]

General Computer Algebra Problems

 {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}

}}}

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