High-Performance Computer Algebra – HPAC

The overall ambition of the project HPAC is to provide international
reference high-performance libraries for exact linear algebra and
algebraic systems on multi-processor architecture and to influence
parallel programming approaches for algebraic computing.

This project gathers researchers working on parallel language and
environments, middleware software engineering, exact linear algebra,
algebraic systems, cryptology and symbolic-numeric verified
computations. The major challenge we will address is the design and
implementation of verified mathematical algorithms with provable,
adaptive and sustainable performance.

LinBox and FGb are two international reference mathematical libraries.
LinBox offers a large panel of functionalities in exact linear algebra
and is used by computer algebra systems such as Sage for instance.
FGb is the reference for Gröbner bases computations usable, for
instance, via Maple.

Both libraries are sequential and rely on exact linear algebra
kernels. The central goal of the HPAC project is to extend their
efficiency to new trend parallel architectures such as clusters of
multi-processor systems and graphics processing units in order to
tackle a broader class of problems in lattice cryptography and
algebraic cryptanalysis.

We conduct our research along three axes:
- A domain specific parallel language (DSL) adapted to high-performance
algebraic computations.
- Parallel linear algebra kernels and higher-level mathematical
algorithms and library modules.
- Library composition and innovative high performance solutions
for cryptology challenges.

A crucial point is that the three above axes are interwoven. Advance
in any axis will contribute to the success of the others and the flow
of new techniques goes in several directions. Indeed, the DSL for
example will be designed in order to implement higher-level
algorithms. These programs will in return foster the optimization of
the DSL in terms of efficiency and its validation for high-performance
algebraic computing.
Our expertise in linear algebra, polynomial system solving, and
cryptology will enable us to focus on state-of-the-art algorithms for
this validation and it will also ensure that the currently best known
algorithms are used both for this validation of the DSL and to address
the cryptology challenges.

More precisely, we expect to produce the following results:
- Open-source parallel building blocks (PBB) for data and task
parallel high performance algebraic computing, whose interface will
define the domain specific parallel language;
- A validation of the integrability of the PBB's into high level
algorithms and of their scalability over various architectures;
- Parallel dense and hybrid dense-sparse matrix multiplication
and decompositions;
- Parallel echelon form over finite fields for cryptographic
dimensions and sizes;
- Higher-level parallel solutions for block-Wiedemann type
algorithms, matrix normal forms, verified linear algebra and
LLL-basis reduction;
- Validation of parallel codes by performance monitoring;
- New releases of FGb and LinBox that include parallel
functionalities;
- Close integration of these libraries in the mainstream
computer algebra systems Sage and Maple, together with
a port toward verified computations in numerical computing
environment such as Scilab and Matlab;
- New theoretical/practical linear algebra algorithms,
publication in journals and/or proceedings of international
conferences of our results;
- New solutions, on distributed testbeds, of cryptographic challenges:
* An accurate estimation of the size of the parameters for
cryptosystems relying on lattice cryptography.
* Dedicated tools for the linear algebra problems generated during
the Gröbner bases computation used in algebraic cryptanalysis.