% $OpenXM: OpenXM/doc/calc2000p/efficient.tex,v 1.2 2000/07/22 08:11:09 noro Exp $
\documentclass{slides}
\usepackage{color}
\usepackage{rgb}
\usepackage{graphicx}
\usepackage{epsfig}
\begin{document}
\parskip 3pt
\fbox{{\huge \color{blue} We Are Efficient}}

{\color {red} Real speedup by parallelism}

Each process can communicate with any other process on {\color{green} MPI}

$\Rightarrow$ {\color{green} Collective operations} similar to \\
{\color{SeaGreen} MPI\_Bcast} and {\color{SeaGreen} MPI\_Reduce}

\vskip 8pt

{\color{red} An example} :
the product of dense univariate polynomials with 3000bit coefficients

\vskip 8pt
{\color{green} Algorithm}(Shoup) : FFT+Chinese Remainder
\vskip 5pt
{\color{green} Parallel computing time} : $O((n\log n)/L+n{\color{red}\log L})$\\
No collective operations : $O((n\log n)/L+n{\color{red}L})$\\
($L$: number of processes, $n$: degree)

\vskip 8pt

\epsfxsize=17cm
\epsffile{3k.ps}
\rightline{ {\color{red} {\tt http://www.openxm.org} }}
\end{document}