Gröbner basis computation is becoming more and more important. In this project, I will implement the fast and efficient algorithms, F4 and F5, to compute Gröbner basis.
These algorithms require efficient symbolic sparse linear algebra computation, which Haskell lacks currently, so implementing such functionality also constitutes the important part of this project.
I will also provide some examples of motivating applications of Gröbner basis which include, for example, non-linear equation system solver.
Gröbner basis computation is becoming more and more important both in the area of pure Math and industry these days. It has a wide variety of application in scientific computation, robotics, cryptology, statistics and many others. For example, if a good performance Groebner basis computation is available, we can implement the following motivating examples:
- Simple pixel-based image layout engine w.r.t. relative constraints. We need to solve integer programming to solve pixel-based constraints, and Groebner basis can be used for it.
- Non-linear equation system solver. Groebner basis techniques can fill in gaps of traditional numerical methods.
There are some implementaion of Gröbner basis computation (such as SINGULAR, Macaulay2, CoCoA, Risa/Asir and FGb/Gb), but none of them are written in Haskell. In addition, most of them are licensed under GPL or for non-commercial purpose only, which prevents industrial use.
If we have the alternative library written in Haskell under more flexible license, it can be reason for mathematicians and industry to adopt Haskell for their projects.
So I have decided to write more sophisticated library utilizing Haskell's progressive language feature (such as nice parallelism, rich type-system, purity and so on). For this purpose, I've been working on my computational-algebra package (repo / Hackage) for about an year, but it's not competitive to existing implementations. To achieve the goals I mentioned above, I will implement more efficient algorithms in this project.
I've already implemented basic tools for computational algebra in computational-algebra package. This includes type-safe multivariate polynomials, Buchberger algorithm to compute Gröbner bases, basic ideal operations and non-linear equation solver using Gröbner basis. F4 algorithm using really naive sparse matrix triangulation is also implemented already. So all I have to do in this project is as follows:
- Implement F5 algorithm with really naive sparse linear algebra, and
- Improve the sparse linear algebra computations.
Both F4 and F5 requires various technique in the are of computer algebra to achieve efficiency. These techinques include for example modular arithmetic and large sparse matrix triangulation. In this project, I will mainly focus on sparse matrix triangulation. These techiniques are not fully described in the original papers, but the author points out some reference to other papers. So I will read such papers and some existing implementations to learn how to implement.
F5 algorithm is fully described in its original paper, so it would not take so long. By the way, F5 itself does not require linear computations at all, but, as indicated in the paper, it achieves more efficiency combined with it. So I will implement the two versions of F5 algorithm:
- Simple version: not involving linear computations, and
- Linear version: involiging linear computations.
After implement both, I will take benchmarks to investigate which is more efficient.
By "triangulation", I mean "reduce rectangular matrix into row-echelon form". Row-echelon form is just the triangular matrix generalized to rectangular form.
There are several package to use dense matrix in Haskell (for example, matrix and repa and so on). But there are only one library to work with sparse matrices with field cofficient: sparse. This library is planned to be improved and I will hopefully build my program on top of it.
The original paper refers to the sparse LU decomposition and the structural Gaussian elimination. Sparse LU decomposition is much harder to implement and we don't need full-fledged LU decomposition, hence I will at first focus on the latter and its derivatives.
- 9 April - 19 May
- Preparation period. Read original and related papers in my free time. One of my majors is computational algebra, so I can also read textbooks in my seminar at university.
- 19 May - 23 June
- Implement F5 algorithm with naive sparse linear algebra computation. This first implementation of sparse matrix triangulation could be much naive. If they are all done, I will implement some examples of applications such as pixel-based image layout engine and non-linear equation system solver.
- 23 June
- Mid-term evaluation. At least F4 and F5 should be implemented together with very naive sparse matrix solver.
- 23 June - 11 Aug
- If examples are not completed, first complete them. Then survey and implement efficient sparse matrix algorithms and optimize them. If there are several possible implementations, I take benchmarks and decide which to adopt. 25 June - 1 July and 31 July - 6 Aug is exam period, so I can hardly write code in those period. If I have spare-time at the end, I would compare Groebner version of equation solution techniques with traditional numerical methods to investigate which fits which kind of inputs.
- 11 Aug
- dead line. At least we have more sufficient matrix triangulation than mid-term.
I'm currently a senior student at Waseda University and become first-year master's degree student at University of Tsukuba on this April. I major in mathematics, especially in the area of computational algebra and axiomatic set theory. I've been studying the theory of Gröbner basis and its application for elimination theory for more than one year.
I'm using Haskell for almost ten years since when I was a junior-highschool student. I've worked for Preferred Infrastructure as a part-time job and written some practical programs in Haskell. I've written many introductory articles on these topics in Japanese. I know both computational algebra and Haskell so I'm the best person for the goal of this project.
I'm especially interested in type-level and template metaprogramming. I've been writing a series of English articles on dependently-typed programming here.
Here are some libraries I maintain or contributed to:
- authenticate-oauth and yesod-auth-oauth
- I created these libraries and had been a maintainer of these until fairly recently.
- equational-reasoning
- A convenient library to write *proofs* of type-level equations.
- type-natural and sized-vector
- Type-level peano numerals and size-parametrized lists.
- computational-algebra
- Computational algebra library. The main goal of this GSoC project is to improve this library.
For other contributions, please see my GitHub page.
- Personal Web Site (Japanese) http://konn-san.com
- Twitter (Japanese) http://twitter.com/mr_konn
- GitHub Page http://github.com/konn
- Contact: [email protected]