Summer school "Advanced techniques in computer algebra systems development"
August 29 - September 2, 2011, University of St Andrews, Scotland
- 1 Topics
- 2 Venue
- 3 Schedule
- 4 List of speakers and abstracts of lectures
- 5 Experience Sessions
- 6 Schedule
- 7 Registration
- 8 Accommodation
- 9 Contacts
- 10 Travelling to St Andrews
- 11 Internet access
- 12 Local information
The summer school '"Advanced techniques in computer algebra systems development" is organised by the Centre of Interdisciplinary Research in Computational Algebra of the University of St Andrews on August 29th - September 2nd, 2011. It is supported by the Scottish Informatics and Computer Science Alliance (SICSA) and the EU FP6 project "SCIEnce - Symbolic Computation Infrastructure for Europe".
Continuing a series of five RISC/SCIEnce training schools in symbolic computation organised in RISC-Linz in 2007-2010, the 2011 school is dedicated to three central themes which are important not only in computer algebra systems, bus also in other scientific software: parallel computations, memory management, and interfaces between systems.
The school will comprise of main lectures given by the invited speakers and of experience sessions where school participants will be able to share their experience. Each of the three days of the school will be centered around one of the thematic areas for the convenience of those interested in a single day participation and/or non-residential registration.
Lectures will take place in the Lecture Theatre A (LTA) in the School of Mathematics and Statistics (North Haugh, St Andrews, Fife KY16 9SS). Refreshment breaks and lunches will be served in Maths 1A. Rooms Maths 1B, 1C may be used as a shortcut to walk between LTA and 1A, and for small groups activities.
You may see the entrance to the School of Mathematics and Statistics under the green door sign using Google Street View.
- Monday, August 29th: Arrival day (no lectures scheduled)
- Tuesday, August 30th: Interfaces (see the programme below)
- Wednesday, August 31st: Memory management (see the programme below)
- Thursday, September 1st: Parallelisaton (see the programme below)
- Friday, September 2nd: Departure day (no lectures scheduled)
List of speakers and abstracts of lectures
- Steve Linton (St Andrews):
- GAP Implementation Fundamentals: The computational algebra system GAP4 was designed, mainly by Martin Schoenert, in the early to mid 1990s. Much of it has remained largely untouched until revisited recently in the context of adding threads to the GAP interpreter. This talk will cover the basic elements of the low-level parts of the design -- memory management, objects and their low-level types, interactions between the C kernel and the GAP interpreter and so on, with a particular emphasis on lessons learned over the years.
- Building a Platform for Parallel Computational Algebra: The HPCGAP project seeks to extend GAP to be an efficient platform for computational algebra users and developers wishing to engage with parallel computing, on hardware ranging from multicore laptops to supercomputers. This talk will report on some aspects of progress to date and plans for the rest of the project.
- Richard Jones (Kent):
- Introduction to garbage collection: In the first of two talks, we shall look at the fundamental algorithms that are the building blocks of all garbage collectors. We shall look at the strengths and weaknesses of different algorithms, how to tune them and consider in particular what requirements a computer algebra system might make of the memory manager.
- The multicore, multiprocessor challenge: In the second talk, we consider how a garbage collector can take efficient advantage of modern, parallel hardware.
- Reimer Behrends (St Andrews), "HPC-GAP: concurrent computational algebra for shared memory systems": This lecture discusses the project of parallelising GAP, a system for computational algebra. Our design aims at making concurrency facilities available for mathematicians without a deep background in parallel programming and concurrency experts alike. To this end, we preserve the appearance of sequentiality, hiding most of the complexity of concurrent programming, by containing each thread within its own separate data space. Parallelism can be exploited through the notion of of migrating objects between data spaces and programming constructs that control concurrent access to shared data. This is done in a fashion that allows library builders to hide the concurrency aspects of their implementations from library users. Our implementation also provides safeguards against typical programming errors, such as race conditions.
- John Abbott (Genova), "Design Features of the CoCoALib": CoCoALib is an open source C++ library for computations in commutative algebra (i.e. principally Groebner bases of polynomial ideals). It is still under active development. Its design aims to combine ease of use, mathematical correctness, efficiency and portability. We shall look at some aspects of the design, and discuss their implications for exception safety and thread safety (though the library itself is currently single threaded).
- Peter Horn (Kassel), Alexander Konovalov (St Andrews): A New Lingua Franca for Symbolic Computation: Easy Composition of Symbolic Computation Software: Several lectures will present the new way of combining computer algebra systems using the Symbolic Computation Software Composability Protocol (SCSCP), in which both protocol messages and data are encoded in the OpenMath format. We will describe SCSCP middleware and APIs, outline some implementations for various Computer Algebra Systems (CAS), and show how SCSCP-compliant components may be combined to solve scientific problems that can not be solved within a single CAS, or may be organised into a system for distributed parallel computations.
- Mickael Gastineau (Paris):
- "Computation in celestial mechanics with SCSCP": We present the SCSCP C/C++ Library which implements the SCSCP protocol and enables applications to provide or access the remote symbolic computations services. Many specialized computer algebra systems dedicated to the celestial mechanics have been developed for many years. These software may provide services for general computer algebra systems. The interest to compute the expansions of the three-body disturbing functions or basic functions of the two-body problem over SCSCP is discussed.
- "Lock-free scalable memory allocators in symbolic computation": Many symbolic computations involve the management of many small fixed or variable size objects, such symbolic expression tree or sparse multivariate polynomials. Memory operations, such as allocation or release, could become a bottleneck for parallel computations. We show how to design scalable explicit memory allocators using the lock-free techniques. Finally, we show the improvements on the scalability and memory footprint usage for the symbolic computations, when these allocators are used.
- "Parallel polynomial operations on multi-cores using work-stealing": Until recently, only sequential polynomials operations were performed. The emergence of desktop computers with multiple cores enables to perform easily parallel computations on polynomials. The work-stealing technique is usually used in order to get the best load-balancing on multiple cores. The parallelizations of the product of sparse multivariate polynomials and Karatsuba algorithm are presented. Finally, the parallelization of the Poisson Bracket will discussed.
- Alexandre Borovik (Manchester), "Computer algebra systems in mathematical education: real life pedagogical challenges" (followed by a panel discussion): The aim of the talk is to cut through misconceptions and unfounded expectations of effects of the use of Information and Communication Technology (ICT) in school and university level mathematical education and initiate a serious professional discussion of the real issues of mathematical education. It is expected that the panel discussion will focus on the ways in which properly adapted computer algebra systems may benefit mathematical educations. Alexandre Borovik is a member of the Education Committee of the London Mathematical Society and is involved in work on the new National Curriculum in mathematics. His views on the use of ICT in university level mathematics education are explained in his paper "IT in university level mathematics teaching and learning: a mathematician's point of view"
- Max Horn (Braunschweig), "Benefits of open source development and open tools": Open source development describes the practice of developing software in an open fashion, given everybody access to not just binary executables, but also the full source code. This is actually quite similar in spirit to the idea of publishing mathematical papers openly, with the express hope that others will read your work and build upon it, thus helping the overall community to thrive and progress. In my talk, I will explain why I believe that open source development is a good and natural idea for mathematical software. Moreover, I will describe how development of mathematical software can benefit from being open, and from using open tools. To this end, I will explain and demonstrate some of the development methods and (free & open) tools that are commonly used in major open source software projects (for things like version control, issue trackers, continuous integration, unit testing, etc.).
- Vladimir Komendantsky (St Andrews), "Tutorial on theorem proving for computational mathematics": The recent advent of theorem proving libraries for constructive mathematics (C-CoRN, coqfinitgroup, Flyspeck, etc.) may set out a new standard of computer algebra where constructive proofs co-exist with computations. In this tutorial, we will discuss some simple but non-trivial examples of proofs and computations in the Coq proof assistant regarding linear algebra and finite group theory. A link with existing computational algebra software such as GAP will be presented in the conclusion.
- Alexander Konovalov (St Andrews), "Distributed parallel computations with GAP": While the HPC-GAP project will allow to run fine-grained parallel programs using the shared memory model with some future version of GAP, I will give an overview of techniques which may be used already now to run coarse-grained parallel computations using the distributed memory model.
- Alexander Voss (St Andrews), "GAPs in the Cloud - Sunshine ahead?": This session will introduce cloud computing and show how GAP servers can be used in a cloud infrastructure like Amazon's EC2 service or the local StACC cloud. The ELVIRA project has developed a system to manage cloud instances from within GAP or other computational algebra tools that support SCSCP communication. You will learn how to create cloud instances from within GAP and run a distributed compute job utilising cloud resources.
If you would like to give a short talk, there will be an opportunity to do this at one of the experience sessions. Participants are encouraged to tell, for example, more details about the internals of the computer algebra system they are involved in, and details about approaches to parallelisation, memory management and interfaces to other systems are particularly welcomed. Please send us the title and a short abstract of your talk to consider its inclusion into the school programme.
The current list of accepted talks:
- Andreas Distler (Lisbon), Really small semigroups, or "How ten semigroups fit in one bit": As part of my PhD studies I enumerated the semigroups with 9 elements and constructed together with James Mitchell a data library for GAP containing all semigroups with at most 8 elements. I will first explain the computer search for semigroups for which I utilised an interface from GAP to the constraint solver Minion. The second part of the talk will be about the construction of the package Smallsemi.
- Attila Egri-Nagy (Eger), "Implementational Issues of the SgpDec GAP Package": SgpDec is a GAP package for the hierarchical compositions and decompositions of transformation semigroups (Krohn-Rhodes Theory) and permutation groups. The current implementation is already capable of coordinatizing semigroups of size tens of thousands. In the talk we describe how this performance is achieved (e.g. using lazily evaluated lists for cartesian products, intensive usage of hashtables, pluggable graph searches, etc.) and how parallelisation could improve efficiency.
- 9:00-9:10 Registration
- 9:10-9:20 Welcome
- 9:20-11:00 Peter Horn, Alexander Konovalov, "A New Lingua Franca for Symbolic Computation: Easy Composition of Symbolic Computation Software". [AK slides] [PH slides]
- 11:00-11:30 Coffee break
- 11:30-12:00 Mickaël Gastineau, "Computation in celestial mechanics with SCSCP" [slides]
- 12:00-13:00 Alexander Konovalov, "SCSCP implementation in GAP" [slides]
- 13:00-14:00 Lunch
- 14:00-15:00 Alexandre Borovik: "Computer algebra systems in mathematical education: real life pedagogical challenges" [slides]
- 15:00-15:30 Concluding panel discussion lead by Alexandre Borovik.
- 15:30-16:00 Tea break
- 16:00-17:00 Vladimir Komendantsky, "Tutorial on theorem proving for computational mathematics"
- 9:15-10:00 Richard Jones, "Introduction to garbage collection" [slides]
- 10:15-11:00 Richard Jones, "The multicore, multiprocessor challenge" [slides]
- 11:00-11:30 Coffee break
- 11:30-12:30 Steve Linton, "GAP Implementation Fundamentals" [slides]
- 12:30-13:00 Mickaël Gastineau, "Lock-free scalable memory allocators in symbolic computation" [slides]
- 13:00-14:00 Lunch
- 14:00-15:00 John Abbott, "Design Features of the CoCoALib"
- 15:00-15:30 Oleksandr Motsak, "Singular memory management" [slides]
- 15:00-15:30 Memory management - concluding discussion
- 15:30-16:00 Tea break
- 16:00-17:00 Max Horn: "Benefits of open source development and open tools". [slides]
- 9:30-10:00 Steve Linton, "Building a Platform for Parallel Computational Algebra" [slides]
- 10:00-11:00 Reimer Behrends, "HPC-GAP: concurrent computational algebra for shared memory systems" [slides]
- 11:00-11:30 Coffee break
- 11:30-12:00 Mickaël Gastineau, "Parallel polynomial operations on multi-cores using work-stealing" [slides]
- 12:00-13:00 Alexander Konovalov, "Distributed parallel computations with GAP" [slides]
- 13:00-14:00 Lunch
- 14:00-15:00 Alexander Voss, "GAPs in the Cloud - Sunshine ahead?" [slides]
- 15:00-15:30 Experience talk: Attila Egri-Nagy, "Implementational Issues of the SgpDec GAP Package"
- 15:30-16:00 Tea break
- 16:00-16:30 Experience talk: Andreas Distler, "Really small semigroups, or "How ten semigroups fit in one bit"" [slides]
- 16:30-17:00 "computer algebra clinic" (questions and answers) and concluding discussion.
In any of the registration categories, participation in the school is free of charge for PhD students studying in Scotland due to the support from SICSA.
For other participants, the registration fees are as follows:
- £300 - full registration, including the registration fee, 4 nights accommodation in the New Hall (which is located in a short walking distance from the school venue, as well as from the main tourist attractions and from the bus station), coffee breaks, breakfasts, lunches and dinners during your stay.
- £150 - non-residential registration, including the registration fee, coffee breaks and lunches during the school days.
- £50 - single day registration (available for one or two days), including the registration fee, coffee breaks and lunch.
We regret that there is no support available for other attendees.
- for the full registration: August 14th 2011
- for the non-residential and single day registration: August 21st 2011
Updated on August 22nd 2011: The online registration for the school has been closed. For a limited number of late registration options, please contact Alexander Konovalov: alexk at mcs.st-andrews.ac.uk
- For participants with the full registration, accommodation will be provided in the New Hall located in a short walking distance from the school venue, as well as from the main tourist attractions and from the bus station.
New Hall North Haugh St Andrews Fife KY16 9XW Tel: 01334 467000 Fax: 01334 467001 Email: email@example.com
Arriving in the New Hall on Monday, you may check in at any time after 3pm. The dinner is served between 6pm and 7pm. If you wish to arrive before 3 pm, it is possible to leave your luggage in the New Hall reception and check in later. The staff at the New Hall reception is available on the 24 hours basis, so there is no problem with arriving late. The check out time on Friday is 10am.
For further information, please contact:
- Alexander Konovalov: alexk at mcs.st-andrews.ac.uk
- Chris Brown: chrisb at cs.st-andrews.ac.uk
- Vladimir Janjic: jv at cs.st-andrews.ac.uk
Travelling to St Andrews
If you arrive to Edinburgh by air, we suggest to take an Airlink 100 bus from the airport to the city centre (Haymarket or Waverley stations) and then take a train from Edinburgh to Leuchars. From Leuchars to St Andrews you may take bus 99 (or 96 which is a bit slower since it takes a different route). A taxi from Leuchars to St Andrews may cost about 10 pounds. The taxi rank is close to the bus stop and normally have several taxis available. In case if there are none, some useful phones to call a taxi:
- Williamsons 01334 476787
- Independent 01334 840331
- Golf City 01334 477788
- Clubcars 01334 838555
Some practical advises:
- Bus tickets may be purchased from the driver
- It is advised to purchase the train ticket at the station, where you may get a discounted price (e.g. an off-peak return ticket dependently on the time of your journey)
- Alternatively, you may cross the Firth of Forth by bus, taking the Jet 747 bus from the airport:
- to Inverkeithing to take a train to Leuchars
- to Ferrytoll Park & Ride to take the direct Stagecoach X59 bus to St Andrews
The decision whether to go to the central Edinburgh or not is a little optimisation problem which solution depends on the time of the day, since the Forth Road Bridge may be very busy in peak hours and not all trains stops in Inverkeithing. Ask local organisers for further advice if necessary.
Finally, you may wish to consider sightseeing in Edinburgh on your way to St Andrews. One extra alternative to get to St Andrews after the peak hours is the Stagecoach X59 bus from the Edinburgh bus station which takes 1 hour 45 minutes. The two last buses at 19:45 and 20:45 require to change a bus in Glenrothes so the journey will take 10 minutes longer. Please be aware that X60 bus also goes to St Andrews but along a different route which is about 45 minutes longer.
- Getting to St Andrews from the University website
- Journey Planner to search for bus and train connections.
- ScotRail website for the trains timetable to travel from Edinburgh to Leuchars by train (select the "Glasgow/Edinburgh - Aberdeen" route)
- Stagecoach East Scotland website for bus 99 timetable to travel between Leuchars and St Andrews
- View of the North Haugh on Google Maps: School of Mathematics and Statistics is the smaller of the two rectangular buildings located to the right of the trapezoid building marked with "A"
- Map of the University in PDF:
- School of Mathematics and Statistics - 14(F3)
- School of Computer Science - 16(F3)
- New Hall - 4 (D3/E3)
- Bus station - 21(H2)
University of St Andrews operates staff parking permits policy. If you arrive by car, please ask local people for an advice about parking places where you can park without parking permit. The recommended choice is the Petheram Bridge car park which provides free parking and is conveniently located for those arriving from North direction by A91.
- Participants staying in the New Hall should ask at the Reception for the internet access account and a network cable if they wish to use it in their rooms. There is also wireless network available in common access areas of the University, but not in the room.
- University of St Andrews supports Eduroam. It allows external visitors to connect, but to be able to login you may need to set up first everything in your home institution.
- MUSA: Museum of the University of St Andrews
- St Andrews Castle
- St Andrews Cathedral
- British Golf museum
- St Andrews Aquarium
Edinburgh International Festival: