Research Activities

My main interest is exact linear algebra algorithms and the underlying arithmetic. One of my primary interests is the analysis of algorithms and the development of the best suited implementations. This includes problems over finite fields such as finding minimal polynomial of matrices and every problem related to, but also problems over the integers like solving systems of linear equations. The development and the maintaining of the "LinBox" library, which is the concretisation of an international joined work around exact linear algebra, remain also two majors objectives in my research.

Publications

Preprints

• Random primes in arithmetic progressions
  P. Giorgi, B. Grenet, A. Perret Du Cray and D. S. Roche
  February 2022

Articles in journals and refereed conference proceedings

• Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations
  Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow and Damien Vergnaud
  Proc. ITC'24: Information-Theoretic-Cryptography, Stanford, CA, USA, LIPIcs - Volume 304, pp. 11:1-11:24, August 2024.
• Fast interpolation and multiplication of unbalanced polynomials
  P. Giorgi, B. Grenet, A. Perret Du Cray and D. S. Roche
  Proc. ISSAC'24: ACM International Symposium on Symbolic and Algebraic Computation, Raleigh, USA, ACM Press, pp. 437--446, July 2024.
• Polynomial modular product verification and its implications.
  P. Giorgi, B. Grenet and A. Perret Du Cray
  Journal of Symbolic Computation - ISSAC'20 special issue, vol 116, pp. 98--129, May 2023.
• Sparse polynomial interpolation and division in soft-linear time
  Awarded with distinguished paper award (SIGSAM announce)
  P. Giorgi, B. Grenet, A. Perret Du Cray and D. S. Roche
  Proc. ISSAC'22: ACM International Symposium on Symbolic and Algebraic Computation, Lille, France, ACM Press, pp. 459-468, July 2022.
• Random primes without primality testing
  P. Giorgi, B. Grenet, A. Perret Du Cray and D. S. Roche
  Proc. ISSAC'22: ACM International Symposium on Symbolic and Algebraic Computation, Lille, France, ACM Press, pp. 207-215, July 2022.
• On exact division and divisibility testing for sparse polynomials.
  P. Giorgi, B. Grenet and A. Perret Du Cray
  Proc. ISSAC'21: ACM International Symposium on Symbolic and Algebraic Computation, St. Petersburg, Russia, ACM Press, pp. 163--170, July 2021.
• Essentially optimal sparse polynomial multiplication.
  P. Giorgi, B. Grenet and A. Perret Du Cray
  Proc. ISSAC'20: ACM International Symposium on Symbolic and Algebraic Computation, Kalamata, Greece, ACM Press, pp. 202--209, July 2020.
• Fast in-place algorithms for polynomial operations: division, evaluation, interpolation.
  P. Giorgi, B. Grenet and D. Roche
  Proc. ISSAC'20: ACM International Symposium on Symbolic and Algebraic Computation, Kalamata, Greece, ACM Press, pp. 210--217, July 2020.
• Generic reductions for in-place polynomial multiplication.
  P. Giorgi, B. Grenet and D. Roche
  Proc. ISSAC'19: ACM International Symposium on Symbolic and Algebraic Computation, Beijing, China. ACM Press, pp. 187--194, July 2019.
• A probabilistic algorithm for verifying polynomial middle product in linear time.
  P. Giorgi
  Information Processing Letters, Volume 139, pp. 30--34, November 2018.
• Certification of minimal approximant bases.
  P. Giorgi and V. Neiger
  Proc. ISSAC'18: ACM International Symposium on Symbolic and Algebraic Computation, New York, USA. ACM Press, pp. 167--174, July 2018.
• Simultaneous conversions with the Residue Number System using linear algebra.
  J Doliskani, P. Giorgi, R. Lebreton and E. Schost.
  ACM Transactions on Mathematical Software, Volume 44, Issue 3, 21 pages , April 2018.
• Recursive double-size fixed precision arithmetic.
  A. Breust, C. Chabot, J.-G. Dumas, L. Fousse and P. Giorgi.
  Proc. ICMS 2016: Fifth International Congress on Mathematical Software, Berlin, Germany. LCNS Volume 9725, pp. 223--231, July 2016.
• Generating Optimized Sparse Matrix Vector Product over Finite Fields
  P. Giorgi and B. Vialla.
  Proc. ICMS 2014: Fourth International Congress on Mathematical Software, Seoul, Korea. LNCS Volume 8592, pp. 685--690, August 2014.
• Elements of Design for Containers and Solutions in the LinBox Library.
  
  B. Boyer, J.-G. Dumas, P. Giorgi, C. Pernet and B. D. Saunders.
  Proc. ICMS 2014: Fourth International Congress on Mathematical Software, Seoul, Korea. LNCS, Volume 8592, pp. 654--662, August 2014
• Online order basis algorithm and its impact on the block Wiedemann algorithm.
  P. Giorgi and R. Lebreton.
  Proc. ISSAC'14: ACM International Symposium on Symbolic and Algebraic Computation, Kobe, Japan. ACM Press, pp. 202--209, July 2014.
• Parallel modular multiplication on multi-core processors.
  P. Giorgi, L. Imbert and T. Izard.
  Proc. ARITH 21: IEEE International Symposium on Computer Arithmetic, Austin, Texas, USA. IEEE Computer Society, pp. 135--142, April 2013.
• On Polynomial Multiplication in Chebyshev Basis.
  P. Giorgi.
  IEEE Transactions on Computers, Volume 61, number 6, pp. 780--789, June 2012.
  Download the code from the paper (gzipped tar)
• Exact Sparse Matrix-Vector Multiplication on GPU's and Multicore Architectures.
  B. Boyer, J.-G. Dumas and P. Giorgi.
  Proc. PASCO'10: Parallel Symbolic Computation, Grenoble, France. ACM Press, pp. 80--88, July 2010.
• Comparison of Modular Arithmetic Algorithms on GPUs.
  P. Giorgi, T. Izard and A. Tisserand.
  Proc. ParCo'09: International Conference on Parallel Computing, Lyon, France. IOS Press, pp. 315--322, September 2009.
  source code; benchmark code (not maintained).
• Optimizing elliptic curve scalar multiplication for small scalars.
  P. Giorgi, L. Imbert and T. Izard.
  Proc. Mathematics for Signal and Information Processing in SPIE'09, San Diego, USA. SPIE Ed., Volume 7444, pp. 74440N (10), August 2009,
• Dense Linear Algebra over Finite Fields: the FFLAS and FFPACK packages.
  J.-G. Dumas, P. Giorgi and C. Pernet.
  ACM Transactions on Mathematical Software, Volume 35, number 3, pp. 19:1--19:42, October 2008.
• Formal proof for delayed finite field arithmetic using floating point operators.
  S. Boldo, M. Daumas and P. Giorgi.
  Proc. RNC'8: 8th Conference on Real Numbers and Computers, Santiago de Compostela, Spain. July 2008.
• Subquadratic Binary Field Multiplier in Double Polynomial System.
  P. Giorgi, C. Nègre and T. Plantard.
  Proc. SECRYPT'2007: International Conference on Security and Cryptography, Barcelona, Spain. INSTICC Press, pp. 229--236, July 2007.
• Parallel Computation of the rank of large sparse matrices from algebraic K-theory.
  J.-G. Dumas, P. Elbaz-Vincent, P. Giorgi and A. Urbanska.
  Proc. PASCO'2007: Parallel Symbolic Computation, London, Ontario, Canada. ACM Press, pp. 43--52, July 2007.
• Faster Inversion and other Black Box Matrix Computation Using Efficient Block Projections.
  W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann and G. Villard.
  Proc. ISSAC'07: ACM International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada. ACM Press, pp. 143--150, July 2007.
• Solving Sparse Rational Linear Systems.
  W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann and G. Villard.
  Proc. ISSAC'06: ACM International Symposium on Symbolic and Algebraic Computation, Genova, Italy. ACM Press, pp. 63--70, July 2006.
• FFPACK: Finite field linear algebra package.
  J.-G. Dumas, P. Giorgi and C. Pernet.
  Proc. ISSAC'04: ACM International Symposium on Symbolic and Algebraic Computation , Santander, Spain. ACM Press, pp. 119-126, July 2004
• On the complexity of polynomial matrix computations.
  Awarded with distinguished student author award (SIGSAM announce)
  P. Giorgi, C.-P. Jeannerod and G. Villard.
  Proc. ISSAC'03: ACM International Symposium on Symbolic and Algebraic Computation , Philadelphia, USA. ACM Press, pp 135-142, August 2003.
• LinBox: A Generic Library for Exact Linear Algebra.
  J.-G. Dumas, T. Gautier, M. Giesbrecht, P. Giorgi, B. Hovinen, E. Kaltofen, B.D. Saunders, W.J. Turner and G. Villard.
  Proc. ICMS'02: International Congress of Mathematical Software, Beijing, China. World Scientific Press, pp. 40-50, August 2002.

Research reports

• P. Giorgi, L. Imbert and T. Izard. Multipartie Modular Multiplication. August 2011.
  

Posters

• Relaxing Order Basis Computation, (Abstract)
  ISSAC'13: International Symposium on Symbolic and Algebraic Computation, Boston, USA, July 2013.
• Implementation of a Las Vegas Integer Matrix Determinant Algorithm, (in ppt )
  ECCAD'05: East Coast Computer Algebra Day (Ashland, USA-Ohio, March 2005)
• LUdivine: A Symbolic block LU factorisation for matrices over finite fields using BLAS,
  ECCAD'03: East Coast Computer Algebra Day (Clemson, USA-South Carolina, April 2003)

Dissertations

• PhD dissertation (advisor: G. Villard)
  Arithmetic and algorithmic in exact linear algebra for the LinBox library (in french).
  Ecole Normale superieure de Lyon, LIP, Lyon, France, December 2004.
  (PDF, PS)
• MSc dissertation (advisor: Pr. J.-C. Bajard )
  Study in RNS basis change (in french)
  Universite Montpellier II, LIRMM, Montpellier, France, July 2001.

Talks

• Fast interpolation and multiplication of unbalanced polynomials
  ECO Seminar - LIRMM (Montpellier, October 15, 2024)
  ISSAC'24: International Symposium on Symbolic and Algebraic Computation (Raleigh, USA, July 16--19 2024)
  
• LinBox: a generic high performance library for exact linear algebra
  Recent Trend in Computer Algebra 2023 Workshop (Lyon, France, June 2023)
  
• Memory-efficient polynomial arithmetic,
  Séminaire CASYS, LJK Université Grenoble Alpes (Grenoble, France, June 2019)
  
• Certification of minimal approximant basis,
  ISSAC'18: International Symposium on Symbolic and Algebraic Computation (New York, USA, July 16--19 2018)
• Toward high performance matrix multiplication for exact computation,
  Séminaire CASYS, LJK Université Joseph Fourier (Grenoble, France, April 2014)
  SIAM Conference on Parallel Processing for Scientific Computing (Portland, USA, February 2014)
• On Polynomial Multiplication Complexity in Chebyshev Basis,
  Séminaire Algorithmes INRIA, INRIA Rocquencourt (Roquencourt, France, November 29 2010)
  Séminaire Arenaire, LIP - ENS Lyon (Lyon, France, June 17 2010)
• Arithmétique modulaire entière en base polynomiale (in french),
  Séminaire CASYS-BIBOP, LJK - Université Joseph Fourier (Grenoble, France, March 15 2007)
• Theory and Practice for Solving Sparse Rational Linear Systems (in french),
  Séminaire LIRMM, département informatique (Montpellier, France, March 8 2007)
• LinBox: évolutions et interactions d'une bibliothèque d'algèbre linéaire exacte (in french),
  Journées Nationales de Calcul Formel 2007 (Luminy, France, February 1, 2007)
• Solving Sparse Rational Linear Systems,
  ISSAC'06: International Symposium on Symbolic and Algebraic Computation (Genova, Italy, July 9-12 2006)
• Solving sparse integer linear systems ,
  Séminaire MOSAIC, laboratoire LMC-IMAG (Grenoble, France, June 21 2006)
  Séminaire DALI, laboratoire LP2A-Perpignan (Perpignan, France, June 27 2006)
• An interface to link the LinBox library to Maple (invited talk),
  ORCCA - Joint Lab Meeting (Waterloo, Canada, October 14 2005)
• Integer linear system solving (invited talk),
  Challenge in Linear and Polynomial Algebra in Symbolic Computation Software (Banff, Canada, October 1-6 2005)
• On the use of polynomial matrix approximant in the block Wiedemann algorithm (invited talk),
  Canadian Mathematical Society meeting (Waterloo, Canada, June 5-7 2005)
• Calculs haute performance en algèbre linéaire exacte ,
  Séminaire CALFOR, laboratoire LIP6-Université Paris VI (Paris, France, May 10 2005)
• Aritmétique et algorithmique en algèbre linéaire exacte pour la bibliothèque LinBox,
  Soutenance de thèse LIP-ENS Lyon (Lyon, France, December 20 2004)
• LinBox: une bibliothèque générique pour l'algèbre linéaire exacte,
  Ecole Jeunes Chercheurs en Algorithmique et Calcul Formel (Grenoble, France, March 29 - April 2 2004)
• LinBox: algèbre linéaire exacte sur les corps finis et applications,
  Séminaire MOSAIC, laboratoire LMC-IMAG (Grenoble, France, March 25 2004)
• From BLAS routines to finite field exact linear algebra solutions, (invited talk)
  ACA'03 : Application on Computer Algebra (Raleigh, USA-North Carolina, July 28-31 2003)
• LinBox: présentation générale et solutions génériques pour l'algèbre linéaire,
  Journée Nationale de Calcul Formel (Luminy, France, January 20-24 2003)
• LinBox: a generic library for exact linear algebra,
  Workshop on open source computer algebra (Lyon, France, May 21-23 2002)
• Arithmétique des corps finis dans la bibliothèque LinBox,
  Journées Arinews (Paris, France, January 23-24 2002)
• Étude des changements de base en RNS,
  Soutenance de DEA LIRMM-Université Montpellier II (Montpellier, France, July 2001)

Projects & Softwares

• FFLAS-FFPACK, finite field linear algebra subroutines/package home page, github page
• Givaro, a C++ library for computer algebra homepage, github page
• LinBox joint CNRS/NSF project on exact linear algebra home page, github page

PhD Students

• 2008-2011: Thomas Izard on software development for efficient arithmetic in cryptography. Currently R&D engineer at Quarkslab.
• 2012-2015: Bastien Vialla on sparse linear algebra and homomorphic encryption. Currently R&D engineer in cryptography at Orange Labs
• 2019-2022: Armelle Perret Du Cray, Algorithm for sparse polynomials: interpolation, arithmetic and identity testing. Currently Postdoc at University of Waterloo (Canada)
• 2023--2026: Lucas Ottow on fast secure multiparty computations. Work in progress.

Collaborators

• LIP6, Sorbonne University: Damien Vergnaud
• IMAG-LJK, Grenoble: Jean-Guillaume Dumas, Clément Pernet
• University of Waterloo: Georges Labahn, Mark Giesbrecht, Eric Schost, Arne Storjohann
• University of Calgary: Wayne Eberly
• LIP-ENS, Lyon: Claude-Pierre Jeannerod, Gilles Villard
• DALI, Perpignan: Christophe Nègre
• IRISA, Lannion: Arnaud Tisserand
• University of Delaware: David Saunders
• US Naval Academy: Daniel S. Roche