Re: [sage-gsoc] Introduction and Questions regarding Optimization and M1RI projects
Martin Albrecht
On Sunday 25 Mar 2012, Duy Nguyen Truong wrote:
> Hi,
>
> I am Truong Duy, a second-year student at the National University of
> Singapore. I am pursuing a double degree program in Mathematics and
> Computer Science.
>
> I am very interested in projects offered by Sage. It is because they
> involve my favorite subjects which are programming, algorithm and
> mathematics. Particularly, in terms of mathematics, my interests are
> Discrete mathematics, optimization, algebra and linear algebra, and number
> theory. I am efficient in programming with C and C++. I have 3-year
> experience in C programming. I have learnt Python for six months. Currently
> I am comfortable with Python programming. I think my strong background in
> mathematics and computer science, as well as my passion for learning, make
> me suitable for Sage projects.
<snip>
> Besides Optimization project, I am also find the M1RI project interesting.
> In this project, we have an algorithm before-hands. And our job is to
> implement this algorithm. Am I right? Would it help if candidate has
> backgrounds in linear algebra? If so, which are particular important topics
> that a candidate needs to pick up?
Yes, there exists algorithms which need implementing:
1) a base case implementation for multiplying 64 x 64 matrices over
GF(3),GF(5),GF(7) really really fast due to Tom Boothby. Tom has code that
produces Cython code for this, which one could modify to generate C instead.
You may want to read http://arxiv.org/abs/0901.1413 because it describes the
key idea
2) On top and around that you'd have to implement utility and highlevel
functions such as addition, comparison, randomisation etc. and Strassen-
Winograd multiplication, Triangular System Solving, Gaussian elimination etc.
Have a look at the M4RI and M4RIE libraries at http://m4ri.sagemath.org for
the general design I would suggest.
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de