INRIA - international

INRIA Program "Associate Teams"

Events:

the joint CADO-ANC workshop ``Recent Advances on Integer Factorization'' took place in Nancy on October 7-9 (just before SAGE Days 10). Both events were partially supported by the ANC Associate Team.

October 17, 2008: activity report for 2008 and renewal form for 2009.

October 9, 2009: activity report for 2009 and renewal form for 2010.

September 28, 2010: final report [administrative part].

Call for 2010

I. DEFINITION

ASSOCIATE TEAM	ANC
selection	2008

INRIA Project-Team: CACAO	Foreign Partner: Computational Mathematics group from Mathematical Sciences Institute (MSI) at Australian National University (ANU)
INRIA Research Center: Nancy - Grand Est INRIA Theme: Sym B (Algebraic and geometric structures, algorithms)	Country: Australia

	French Coordinator	Foreign Coordinator
Name, Surname	Zimmermann, Paul	Brent, Richard
Position	Research Director	ARC Federation Fellow
Institute	INRIA	ANU, Mathematical Sciences Institute
Postal Address	615 rue du jardin botanique, 54600 Villers-lès-Nancy	Canberra, ACT 0200, Australia
URL	http://www.loria.fr/~zimmerma/	http://wwwmaths.anu.edu.au/~brent/
Phone	+33 (0)3 83 59 30 41	(61-2) 6125 3873
Fax	+33 (0)3 83 27 83 19	(61-2) 6125 5549
Email	zimmerma {at} loria [dot] fr	Richard [dot] Brent {at} maths [dot] anu [dot] edu [dot] au

The proposal in brief

Title of the collaboration (in english and french):Algorithms, Numbers, Computers (Algorithmes, Nombres, Ordinateurs)

Description : We propose to join the research efforts of the Computational Mathematics group at ANU (Australian National University, Canberra, Australia) with those of the CACAO team from the ``Centre de Recherche INRIA Nancy-Grand Est'' (Nancy, France) into an INRIA associate team called ANC (Algorithms, Numbers, Computers). We wish to extend in such a way a long-term and successful cooperation between Richard Brent and Paul Zimmermann to all members of both teams, in particular young researchers. The support of the ANC associate team will allow to reinforce that cooperation, especially in the following common scientific projects: Smooth Triangular Numbers (Størmer's Problem), Efficient Finite-Field Arithmetic, Fast evaluation of trigonometric functions, and Modern Computer Arithmetic.

Presentation of the Associate Team

1. Presentation of the foreign coordinator
Richard Brent did his Master of Science and his PhD at Stanford University, in 1970 and 1971. He was appointed Foundation Professor of Computer Science at the Australian National University in 1978. In March 1998 he became the Statutory Professor of Computing Science in the University of Oxford. In March 2005 he took up a 5-year position as ARC Federation Fellow in the Mathematical Sciences Institute and the Research School of Information Sciences and Engineering at the Australian National University. He is also a Chief Investigator in the ARC Centre of Excellence for Mathematics and Statistics of Complex Systems (MASCOS) and head of the Computational Mathematics group in the Mathematical Sciences Institute at ANU (more details).
2. History of the collaboration

2.1. Between both teams: see auxiliary document

2.2. Between INRIA and ANU: To our best knowledge, there are two common projects between INRIA and ANU, and one existing associate team with an Australian partner:

a CNRS PICS project between the LAGADIC project-team (Rennes), ANU (Robert Mahony) and CSIRO in Brisbane (Peter Corke and Jonathan Roberts), which started in 2006, on visual servo-control of unmanned aerial vehicles;

a international Marie Curie project between the S4 project-team (Rennes) and ANU (Sylvie Thiébaux), on Formal methods for multi agents systems (ends in 2007);

the associate team Internet Probing between the TREC project-team (Rocquencourt) and the University of Melbourne (Darryl Veitch), which started in 2007;

See also the Australia page of INRIA's DRI (in french).

3. Impact : Indicate to what extent, in your own opinion, this associate team would have an important impact:

3.1. on the existing collaboration with your partner : Since the return of Richard Brent to Australia in 2005, funding regular visits is more expensive. Our aim is to secure our strong collaboration in the future, and to extend it to all researchers of the Computational Mathematics and CACAO groups, in particular young researchers (PhD students, postdocs).

3.2. on the collaboration with other INRIA project-teams: we expect the visits of the Australian partners will interest other INRIA project-teams of the Sym B theme, in particular ALGO and TANC

3.3. on the collaboration with other research teams from the foreign institution : some common interests on Fast Fourier Transform and Block Algorithms are shared with the group of Markus Hegland (ANU, Mathematical Sciences Institute); on combinatorial algorithms and asymptotic combinatorics, some discussions might happen with Brendan McKay (ANU, Computer Science Department)

4. Miscellaneous: any other useful information.

II. PREVISIONS for 2008

Work Plan

(see Section 3 of the auxiliary document for more details)

Initial contact between the participants The main objective for 2008 will be that the participants meet each other. Indeed, so far only the two coordinators know (part of) the participants of the other team. We expect several discussions will follow, some research directions will emerge from the subjects outlined below, and most probably new ideas will come up.
Smooth Triangular Numbers (Størmer's Problem) The main goal here is the multiple-precision computation of logarithms of integers. This is related to an algorithm designed by Lehmer to solve Størmer's Problem (find consecutive integers n and n+1 that are simultaneously smooth). We aim to follow a new approach, suggested by Baker's theory of linear forms. This would initially address the fundamental question: can this approach provide a practical alternative to the "Pell-driven" method of Størmer/Lehmer?
Efficient Finite-Field Arithmetic Since 2006, P. Gaudry and E. Thomé started to develop a new library (MPFQ) for the arithmetic over finite fields. During R. Brent's visit in Nancy in May 2007, some new algorithms were found for the base-case multiplication of binary polynomials. In 2007-2008, we will write a paper explaining those new algorithms, together with some variants of Toom-Cook's algorithm in that case. In the medium term, we expect that several discussions will happen with Gaudry, Thomé and Arndt about efficient bit-operations, around the MPFQ library and the on-line book Algorithms for programmers from J. Arndt.
Fast Evaluation of Trigonometric Functions The efficient evaluation of trigonometric functions (sin, cos, tan) is a key problem for developers of arbitrary precision libraries like MPFR. Since the Many Digits competition, several discussions arose between the team members. We plan to analyze in details several algorithms, which means comparing their asymptotic complexity, their range of usage (both in terms of precision and of input domain), and implementing them carefully in the MPFR library to compare them experimentally.
Book Modern Computer Arithmetic The main goal of this book (in preparation) is not only to describe the best algorithms at high-level, but really to work out the nasty details that make the difference between a rough description and a detailed pseudo-code that can be readily implemented by a programmer. In 2008, we plan to make a full pass on Chapter 1 (Integer Arithmetic) to check coherence between the different notations and algorithms, and to complete its ``Notes and further references'' section. Chapter 2 (Modular Arithmetic and Finite Fields): we want to add several important algorithms which are still missing, and to complete the ``Exercises'' and ``Notes and further references'' sections need.

In all the above themes, some output is expected, either as co-written scientific publications, and/or by co-developed software tools.

Planned Budget for 2008

1. Co-funding

- Does this cooperation already benefit from INRIA support, or from the foreign partner institution, or from a third-party (European project, NSF, ...)?
No, so far our visits were supported by the budget of the SPACES and CACAO project-teams on the Nancy side.
- In case your proposal is supported, do you expect a symmetric support from the foreign partner institution?
Yes, the visits of Richard Brent to Nancy (as past visits already were) will be supported by the Australian Research Council (ARC) grant.

ESTIMATE OF CO-FUNDINGS
Institute	Amount
ARC (Australian Research Council)	3100 Euros




Total	3100 Euros

2. Exchanges

(see Section 3 and 4 of the auxiliary document for more details)

ESTIMATE OF EXPENSES		Amount (in Euros)
	Number	Accomodation	Travel	Total
Senior Researcher	3	4500	4800	9300
Post-doc	2	4800	3200	8000
PhD student	1	2400	1600	4000
Student
Other (detail) :	2	500	400	1000
Total	7	12300	10000	22300
		- co-funding total		3100
	Amount "Associate Team" expected			19200 Euros for 2008

Remarks or observations:

The above amounts represent real costs, based on our experience with previous visits. In particular, they assume the planes tickets are bought several months in advance. See more details in the auxiliary document, Section 4.
The "Other" line corresponds to the invitation of Arjen Lenstra and Thorsten Kleinjung in Nancy, to organize a mini-workshop on Recent Advances in Integer Factorization