[Jprogramming] Joey's %. benchmark

[Roger Hui]

Arggh!  Mixed up APL and J.  Conventionally, matrix mult is O(n^3), at the
time of my M.Sc. O(n^2^.7), now O(n^2.3728639) according to Wikipedia.

A further personal note:  The recursive QR and a couple of similar
decompositions are how I got to Erdős 2.


On Sun, Sep 8, 2019 at 1:37 PM Roger Hui <rogerhui.canada at gmail.com> wrote:

> A J model of the QR decomposition can be found in
> http://code.jsoftware.com/wiki/Essays/QR_Decomposition
>
> > He builded better than he knew: it relies on +/ .* for most of the
> numeric work.
>
> (Ahem) actually I knew.  It was part of my M.Sc. thesis and is another
> lemma which shows that %.x has the same order of complexity as +/ .* , at
> the time O(n*2^.7) (better than the conventional O(n*3)), now down to
> O(n*2.3728639) according to Wikipedia.  The algorithm is also good answer
> to claims that QR and other matrix decompositions are inherently loopy.
> See Hui & Iverson, _A Note on Programming Style_, Vector, volume 12, number
> 13, 1996-01.
>
>
>
>
>
> On Sun, Sep 8, 2019 at 1:14 PM Henry Rich <henryhrich at gmail.com> wrote:
>
>> For years Joey Tuttle has used the performance of (%. y) as a simple
>> measure of the performance of J releases.  It has improved pretty
>> steadily.
>>
>> This surprised me, because I know where the gaussian-elimination code
>> is, and that code doesn't do much except C loops that do add and
>> subtract.  I didn't see how improvements to the JE would have any effect
>> on (%. y).  Not wanting to mess up a good story, I kept my doubts to
>> myself.
>>
>> Finally I understand.  The code I had been looking at is used only for
>> rational matrices.  The code for general (%. y) is a lovely little
>> recursive QR decomposition that does lots of memory allocation and calls
>> to internal J arithmetic functions.  In fact, it's a pretty good
>> exercise of the computational side of the system.  It's quite short but
>> uses general utilities so that it works on all fixed-precision numeric
>> types.  Bravo to Roger.  He builded better than he knew: it relies on +/
>> . * for most of the numeric work, and that code has now been polished so
>> well that it is the most efficient code in the system.
>>
>> Long live Joey's benchmark!
>>
>> Henry Rich
>>
>> ---
>> This email has been checked for viruses by AVG.
>> https://www.avg.com
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
>