[xquery-talk] Matrix Multiplication (JSONiq)

[Ghislain Fourny]

Hi,

With a naive parallelism approach (on $i and $j), I think it's possible to bring it down to O(N) with a constant cost (in dollars), assuming "full cloud elasticity" (i.e., the number of instances that can be triggered up is not the bottleneck).

The 28.io platform should supports this (disclaimer: it's my employer).

Kind regards,
Ghislain


On 03 Feb 2014, at 12:30, jean-marc Mercier <jeanmarc.mercier at gmail.com> wrote:

> Hi all,
> 
> I've tried the following JSON query with zorba, mimicking a NxN, with N=200, matrix multiplications. Time is 10 sec on http://try.zorba.io/, behaving with a cubic N^3 complexitity.
> Do you really want to know what are the performances of standard linear algebra library for such matrix multiplications ?
> 
> 
> 
> 
> import module namespace datetime = "http://www.zorba-xquery.com/modules/datetime";
> 
> declare variable $size := 200;
> 
> declare variable $A := [ for $i in 1 to $size return 
>     [
>         for $j in 1 to $size return $i*$size+$j
>     ]
> ];
> 
> let $R := ( datetime:current-time(), 
>   [
>     for $i in 1 to count(jn:members($A)) return
>     [
>       for $k in 1 to count(jn:members($A)) return
>         fn:sum(
>           for $j in 1 to count(jn:members($A)) return 
>             $A($i)($j) * $A($j)($k)
>         )
>     ]
>   ]
> , datetime:current-time() )
> 
> return $R[count($R)] - $R[1]
> 
> 
> 2014-02-03 David Carlisle <davidc at nag.co.uk>:
> On 03/02/2014 10:56, Hermann Stamm-Wilbrandt wrote:
> PT1.713634S (JSONiq) versus PT9.77805S (XQuery)
> 
> 
> ooh interesting , I wonder where the bottleneck in the xquery is.
> Probably as Michael commented at some point earlier in the thread, the
> time to access the ith element of a sequence $a[$i].
> 
> 
> But the language doesn't _need_ to change, just if more people did it
> the xquery compilers would perhaps look out for sequences that are
> exclusively accessed via numeric filters and implement them in a way
> that gives constant time access. Having a separate array type does give
> them a big hint though:-)
> 
> David
> 
> 
> ________________________________________________________________________
> The Numerical Algorithms Group Ltd is a company registered in England
> and Wales with company number 1249803. The registered office is:
> Wilkinson House, Jordan Hill Road, Oxford OX2 8DR, United Kingdom.
> 
> This e-mail has been scanned for all viruses by Star. The service is
> powered by MessageLabs. ________________________________________________________________________
> _______________________________________________
> talk at x-query.com
> http://x-query.com/mailman/listinfo/talk
> 
> _______________________________________________
> talk at x-query.com
> http://x-query.com/mailman/listinfo/talk