Re: [boost] A possible GSOC 2011 proposal idea

Subject: Re: [boost] A possible GSOC 2011 proposal idea
From: Chad Seibert (chadjseibert_at_[hidden])
Date: 2011-03-21 07:00:27

Hi,

First of all, many thanks for the feedback! Much of the discussion has been
in whether it is possible for me to accomplish such a task over the summer.
The answer is no; a library designed to meet Boost's standards will not be
done over the summer. However, a substantial amount of the work will be done
over the summer and it will continue over the next year until it is
satisfactory. I will then be responsible for maintaining it for as long as
required.

In order for you to understand the scope of this project, it must be made
clear that the project references itself many times. For example, MILP's and
ILP's are solved using the exact same algorithms, so for all intents and
purposes, they are the same. Second of all, solving ILP's using branch and
bound or cutting planes both require a strong algorithm for solving their
relaxed forms, i.e. their LP relaxations. Third, the bulk of the effort in
solving LP's using the refined simplex algorithm is in solving a system of
linear equations.

This is by far the most difficult part of the entire project and is what I
intend to spend the summer doing. It will be difficult for the
aforementioned reasons; hence the topic of my GSOC proposal will be
efficiently solving linear systems (LS). After GSOC, I will continue my work
and write LP and ILP solvers.

As for the scope of solving LS, there are many different algorithms designed
to do just that. In order to limit the scope, I will not consider parallel
algorithms or distributed algorithms. If the Boost community thinks that
these are reasonable and I should forgo solving LP in favor of solving large
(> 100,000x100,000) LS, we can certainly discuss this. The following
algorithms are up for consideration:

* LU decomposition for small matrices
* Iterative methods for large matrices, such as conjugate gradient for
positive definite matrices

Of course, this will all be integrated into the already existing uBLAS
library. There are many issues with getting such solver to work well in
practice, namely reducing fill-in, numerical stability, and performance. In
any case, getting a general purpose LS solver is the first step towards
getting an LP solver running. Therefore, it is the focus of my work this
summer and only afterwards will I work on LP-related algorithms.

One last this is that it wasn't my intent for my pre-GSOC submission to be
anywhere the quality required for Boost submission. It was only there to
show my support towards this project and that I'm committed fully to its
success.

Thanks again for your feedback!
Chad