m1ri GSOC
Tom Boothby
implement m1ri for a GSOC project.
Venkatesh -- regarding your questions at http://pastebin.com/BveAfvxy
1) The vec3 struct has two members: long u,s. They stand for "unit"
and "sign" respectively. The reason for this is that the bit
representation corresponds to -1,0,1. The 'u' bit is on for -1 and 1
('unit' means 'not zero' in a field), and the 's' bit is on for -1
only (sign is negative). For that block of input, I make the (perhaps
flawed assumption) that if an element is neither 0 nor 2, then it's 1.
This is fine for good input.
2) The output is kinda cheeky, but very very good to understand. In
most fonts, the lower dot in a colon lines up perfectly with a period.
Thus, ':' corresponds to "both bits set", '.' corresponds to "unit
bit set", and ' ' corresponds to "both bits off". Thus, the output
...: ::::: : ..:::.: :.:..:.... :.
shows you exactly which bits in v.s and v.u are on: read the top row
for s, bottom row for u.
On Tue, Mar 20, 2012 at 8:13 AM, Martin Albrecht
<martinr...@googlemail.com> wrote:
> Hi,
>
> 1) @Tom FYI here are a few messages that Venkatesh and I exchanged.
>
> 2) Shall we move this to [m4ri-devel] so it's public (as GSoC asks us to make
> our conversations public as much as possible?)
>
> --
> 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
>
>
> ---------- Forwarded message ----------
> From: Venkatesh Halli <venkatesh...@gmail.com>
> To: Martin Albrecht <martinr...@googlemail.com>
> Cc:
> Date: Sun, 18 Mar 2012 23:07:34 +0530
> Subject: Re: GSoC 2012 - M1RI
> OK, I have good Python and C/C++ knowledge. But I haven't used Sage much (found out about it last week)
> and I'll have to check out Cython. Do you think it'd make sense for me to apply?
>
> (More about me : I'm a Second Year Computer Engineering student at the University of Pune, India.
> Interests include programming, electronics, a bit of math [and Project Euler :P ] )
>
>
> On 18 March 2012 22:53, Martin Albrecht <martinr...@googlemail.com> wrote:
>>
>> Hey,
>>
>> On Sunday 18 Mar 2012, you wrote:
>> > Hello, I'm interested in the M1RI project idea for GSoC-2012.
>>
>> That's great.
>>
>> > Would you be able to provide a sample worksheet written by Tom? I'd like to
>> > try things before applying for the project.
>>
>> I've attached the code Tom sent me a while back. I've CCed Tom to this e-mail
>> so he can share the worksheet if there is stuff that is newer/better/etc.
>>
>> > Also, a more in-depth description of the project, if possible, would be
>> > nice.
>>
>> So, essentially what I envisage is the equivalent of M4RI
>> (http://m4ri.sagemath.org) for p=3,5,7, hence M1RI. It's probably unrealistic
>> to expect to have everything in M4RI at the end of the project, but a solid
>> foundation would be good:
>> - simple stuff: addition/stacking/augmenting/comparing
>> - asymptotically fast multiplication
>> - (triangular system solving)
>> - (Gaussian elimination)
>>
>> > Thanks!
>>
>> Let me know if you have more questions.
>>
>> Cheers,
>> Martin
>>
>> PS: Tom, any objections?
>>
>> --
>> 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
>
>
>
>
> ---------- Forwarded message ----------
> From: Martin Albrecht <martinr...@googlemail.com>
> To: Venkatesh Halli <venkatesh...@gmail.com>
> Cc:
> Date: Sun, 18 Mar 2012 18:23:24 +0000
> Subject: Re: Re: GSoC 2012 - M1RI
> Hey,
>
> On Sunday 18 Mar 2012, Venkatesh Halli wrote:
>> OK, I have good Python and C/C++ knowledge. But I haven't used Sage much
>> (found out about it last week)
>> and I'll have to check out Cython. Do you think it'd make sense for me to
>> apply?
>
> If you know Python and C, you'll have no trouble with Cython. It's something
> that looks like Python but gets compiled to C. What kind of projects involving
> C did you do? Also, as far as I can see you'd mainly have to *read* Cython
> code - i.e., Toms - and write C code (I prefer C over C++ for this). The point
> of this project is to produce a C library which can then be used by Sage.
> Writing the interface to said library is very very easy, so I wouldn't worry
> about it.
>
>> (More about me : I'm a Second Year Computer Engineering student at the
>> University of Pune, India.
>> Interests include programming, electronics, a bit of math [and Project
>> Euler :P ] )
>
> I think for this project relevant skills would be:
> - low-level C knowledge (bit-fiddling stuff)
> - some knowledge about autotools (to produce the library) but one can pick
> those up on the road I guess
> - a bit of knowledge about linear algebra
> - a fascination for writing fast code,e.g. patients to figure out bottlenecks
> via profilers etc.
>
> Perhaps a good test to find out whether this is your project: figure out Tom's
> matrix format and write a function in C that adds matrices in this format.
>
> I hope this is helpful at all,
> 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
>
>
> ---------- Forwarded message ----------
> From: Venkatesh Halli <venkatesh...@gmail.com>
> To: Martin Albrecht <martinr...@googlemail.com>
> Cc:
> Date: Mon, 19 Mar 2012 09:11:43 +0530
> Subject: Re: Re: GSoC 2012 - M1RI
>
>> I think for this project relevant skills would be:
>> - low-level C knowledge (bit-fiddling stuff)
>> - some knowledge about autotools (to produce the library) but one can pick
>> those up on the road I guess
>> - a bit of knowledge about linear algebra
>> - a fascination for writing fast code,e.g. patients to figure out bottlenecks
>> via profilers etc.
>>
>
> Then the only things I'll need to work on are autotools, and Cython.
>
>>
>> Perhaps a good test to find out whether this is your project: figure out Tom's
>> matrix format and write a function in C that adds matrices in this format.
>
>
> No problem. It's college time now, so I'll get back to you later.
> (BTW, thank you for being so helpful. This is the first time I'm doing an open source project.)
>
>
>
> ---------- Forwarded message ----------
> From: Venkatesh Halli <venkatesh...@gmail.com>
> To: Martin Albrecht <martinr...@googlemail.com>
> Cc:
> Date: Mon, 19 Mar 2012 22:48:57 +0530
> Subject: Re: Re: GSoC 2012 - M1RI
> Hi, I checked out the arith.pxi and io.pxi files from the example set you sent me. I do not understand quite a lot of it.
> I think I need to be spoon-fed for a bit. Here's a link to a bit of the stuff I didn't understand.
> http://pastebin.com/BveAfvxy
>
> Also, is there already some code that has been translated to C? If not, would you be able to spare some time to
> write it for me?(possibly the addition function.) That would help a lot.
>
> Thanks!
>
> P.S - I'm sorry if you think I'm pestering you too much. This is my first time, I'd like to learn as much as I can.
>
>
> On 19 March 2012 09:11, Venkatesh Halli <venkatesh...@gmail.com> wrote:
>>
>>
>>> I think for this project relevant skills would be:
>>> - low-level C knowledge (bit-fiddling stuff)
>>> - some knowledge about autotools (to produce the library) but one can pick
>>> those up on the road I guess
>>> - a bit of knowledge about linear algebra
>>> - a fascination for writing fast code,e.g. patients to figure out bottlenecks
>>> via profilers etc.
>>>
>>
>> Then the only things I'll need to work on are autotools, and Cython.
>>
>>>
>>> Perhaps a good test to find out whether this is your project: figure out Tom's
>>> matrix format and write a function in C that adds matrices in this format.
>>
>>
>> No problem. It's college time now, so I'll get back to you later.
>> (BTW, thank you for being so helpful. This is the first time I'm doing an open source project.)
>>
>
>
>
> ---------- Forwarded message ----------
> From: Martin Albrecht <martinr...@googlemail.com>
> To: Venkatesh Halli <venkatesh...@gmail.com>
> Cc:
> Date: Mon, 19 Mar 2012 17:55:01 +0000
> Subject: Re: Re: Re: GSoC 2012 - M1RI
> Hi,
>
> On Monday 19 Mar 2012, you wrote:
>> Hi, I checked out the arith.pxi and io.pxi files from the example set you
>> sent me. I do not understand quite a lot of it.
>
> I just realised, sorry, that I probably should have pointed you to:
>
> http://arxiv.org/abs/0901.1413
>
> where the key ideas are highlighted, this should help you to get started
> better.
>
>> I think I need to be spoon-fed for a bit. Here's a link to a bit of the
>> stuff I didn't understand.
>> http://pastebin.com/BveAfvxy
>
> As far as I can tell - I didn't write this code - u and s hold the components
> of the elements. Recall that we are computing e.g. mod 3 so we need two bits
> to store elements. These bits are stored in u and s in a format that makes
> arithmetic cheap (see the arXiv paper linked above).
>
>> Also, is there already some code that has been translated to C?
>
> Unfortunately, no.
>
>> If not, would you be able to spare some time to
>> write it for me?(possibly the addition function.) That would help a lot.
>
> Unfortunately, I won't have the time to do that for you in the near future.
> Perhaps a different strategy would be good: you read the paper I linked above
> and try to implement the idea independently in C. Then, you can revisit Tom's
> .pxi files to figure out if/what he does differently? Once you get stated I
> can try to give tips & answer questions should you have any? Is that a viable
> plan for you?
>
>> Thanks!
>>
>> P.S - I'm sorry if you think I'm pestering you too much. This is my first
>> time, I'd like to learn as much as I can.
>
> No need to feel bad about it, really! I realise this is a rather ambitious
> project, and now feel bad for not being much for helpful. But to perhaps
> motivate you for it further; if successful I'm sure there's a research paper
> in a good journal in it :)
>
> 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
>
>
> ---------- Forwarded message ----------
> From: Venkatesh Halli <venkatesh...@gmail.com>
> To: Martin Albrecht <martinr...@googlemail.com>
> Cc:
> Date: Tue, 20 Mar 2012 20:06:44 +0530
> Subject: Re: Re: Re: GSoC 2012 - M1RI
>
>>
>> Unfortunately, I won't have the time to do that for you in the near future.
>> Perhaps a different strategy would be good: you read the paper I linked above
>> and try to implement the idea independently in C. Then, you can revisit Tom's
>> .pxi files to figure out if/what he does differently? Once you get stated I
>> can try to give tips & answer questions should you have any? Is that a viable
>> plan for you?
>
>
> OK, sounds good. I'll work in this. Really looking forward to finishing the library, after GSoC too :)
>
Martin Albrecht
Burcin just reminded me that we should CC the Sage GSOC mailing list so that
other (potential) mentors can see what we're discussing/up to. So I'm CCing
[sage-gsoc] as well, sorry for the noise, just trying to follow protocol here
:)
Tom Boothby
fast as it is ugly.
I actually have some python code sitting around which automagically
finds the right parameters, and spits out the method mul_64. It's
currently too ugly to be shared, but it can generate optimal* code for
any set of dimensions up to 64. This will be useful for matrices
whose dimensions are not a multiple of 64.
*actually... it generates code which uses the smallest possible number
of bit operations. That just so happens to line up with 'fastest
choice of parameters' wherever I've tested it. Some automatic tuning
may be useful as the code gets more complex.
On Tue, Mar 20, 2012 at 3:22 PM, Martin Albrecht
Martin Albrecht
note that the deadline for submitting proposal is this Friday. If you want
feedback before the deadline you should put your proposal on google-melange
soon-ish.