There is no need for the representation of a matrix in anything more than 1 dimension.
A two dimensional m x n matrix can be represented by a 1 dimensional array of length (m * n) + 1 where the + 1 is used to recorded the size of the m (or if you choose) n axis. Suppose your matrix was 10 by n. If you have a representation that stores the fact that the matrix has 10 rows fact then it follows that the item at index position 704 has row column coordinates of 71, 4. Alternatively if it instead you chose to store that it had say 5 columns then index 704 has coordinates 141, 4. This extends to n dimensions. A n-dimensional matrix can be represented by an (m1 * m2 * ......* mn) + n-1 array. Take the three dimensional case, with the previous example. We will take the 3rd dimension as page. In our representation the extra numbers represent m and m*n. Take m as 10, n as 5 so our array has 10 and 500 tagged on to it. Given an index of 3683, divide by m*n to give the page (8) then and use the remainder to figure out you are on row 19 column 3. So the x,y, z coordinates of that index are 19,3,8. You can extend this principle to any number of dimensions. Having said that I am still going to target SQL On Tue, Dec 31, 2013 at 4:38 PM, David Lee <[email protected]> wrote: > There is a core limitation in XQuery 3.0 data types that make 2+D > matrixes painful. > > That is sequences cannot nest, they automatically flatten. > > e.g. > > ( ( 1 , 2 , 3 ) , (4 , 5 , 6) ) > > becomes > > ( 1,2,3,4,5,6) > > > > So there is no natural datatype for matrix (> 1D) > > > > You can implement them with elements or functions but both impose an > overhead that is harder for the optimizer to get rid of. > > e.g. as elements (arbitrary name chosen) > > > > let $a := <c> > > <c> > > <c>1</c> > > <c>2</c> > > <c>3</c> > > </c> > > <c> > > <c>4</c> > > <c>5</c> > > <c>6</c> > > </c> > > </c> > > return $a/c[2]/c[2] > > > > Or as functions > > > > let $a := ( function () { (1,2,3) } , function () { (4,5,6) } ) > > return $a[2]()[2] > > > > > > Both return 5 > > > > > > The syntax is a bit cumbersome but it works ... its also hard on the > optimizer > > > > This among other reasons (such as supporting json arrays) is why native > array types that can nest are often supported as vendor extensions, > > and I belive are being considered by W3C as XQuery native types. > > > > > > > > > > > > > > > > > > > > > > > > > > > > *From:* [email protected] [mailto:[email protected]] *On > Behalf Of *Michael Sokolov > *Sent:* Tuesday, December 31, 2013 10:49 AM > *To:* jean-marc Mercier; Andrew Welch > *Cc:* xquery-discuss; ihe onwuka > *Subject:* Re: [xquery-talk] Matrix Multiplication > > > > I would love to see some tests of pure XQuery implementations of both > sparse and dense operations. I suspect performance of matrix multiply, > inversion, etc, will be poorer than in C++ or Java, but I would expect > performance comparable to Perl or Python (w/o its numpy extension) - just a > wild guess. I'd also expect it might be easier to get good sparse > performance. I don't know why, just a hunch. > > But the more interesting question for me is whether language changes are > really needed to support this. I would have thought that proper > optimization of operations on sequences would be enough? So for example, > an extension module using sequences as matrix datatypes could possibly > optimize performance using a lower-level implementation. Does anyone see > any reason why that wouldn't be possible? > > -Mike > > PS: > I reviewed the discussion you referred to, jean-marc, but it seems to have > more to do with using functions as map keys, and I don't see any direct > connection to linear algebra? > > On 12/31/2013 9:55 AM, jean-marc Mercier wrote: > > It is not due to the spec. It is rather due to the common usage of > XQUERY, forcing vendor solutions (as BaseX) to focus primarily on XML Data > Base requests more than algorithmic performances. > > > > There are actually some threads that are discussing these performance > issues in the context of maps (maps are for instance used for sparse matrix > representations) : look for instance to ""map module for XQUERY ?" that I > initiated or "Higher-order XQuery Modules" by Leo from BaseX, on talk@ > x-query.com mailing list. > > Anyhow, to write a serious linear algebra modulus, the basic need is to > have a vector containers. Unfortunately, XQUERY does not provide any > performant vector containers at present time, and it is not possible to > code them in pure XQUERY : I have tried, and more experienced xquery > developpers than me have also tried, without success. > > > > We have to wait for the XQUERY version that will give us these containers, > a decision to be taken by the W3C. > > > > > > 2013/12/31 Andrew Welch <[email protected]> > > > Are you saying the spec as it stands somehow forces all implementations to > be 1000x slower, or just what you have observed in some particular > implementation? > > On 31 Dec 2013 14:27, "jean-marc Mercier" <[email protected]> > wrote: > > > > As far as I understand, you want to write a linear algebra module using > XQUERY ? > > If so, I opened a thread some months ago about this idea. My opinion > today is that this is a false good idea at present time. > > > > 1) XQUERY would be really good for writing concise, efficient linear > algebra modulus. > > 2) However, I strongly recommend to wait a little bit for starting > coding : the current version of XQUERY (3.0) suffers from performance > issues. A linear algebra modulus written in XQUERY is expected to have > performances performances 1000 X slower than its corresponding C++ or JAVA > (you can measure it precisely). Any mathematician linear algebra modulus > would probably trashed your modulus after the first test. > > > > Hope this helps > > > > > > > > 2013/12/31 Ihe Onwuka <[email protected]> > >> > >> Assuming a sparse representation it is about 4 lines of SQL. This is > known not least because you can read enough articles and papers that > discuss it and it optimises well. The obvious google search does not reveal > any corresponding XQuery discussion, neither does it appear to have > surfaced on this or the eXist mailing list (allowing for my deficient > search skills). For something so "trivial" I thought that was rather > strange. Hence I thought it would be prudent to ask before naively > embarking on a 600k X 40k matrix multiplication. > >> > >> > >> > >> On Tue, Dec 31, 2013 at 11:31 AM, Andrew Welch < > [email protected]> wrote: > >>> > >>> > >>> It should be pretty trivial... > >>> > >>> On 31 Dec 2013 11:07, "Ihe Onwuka" <[email protected]> wrote: > >>> > > >>> > Has anybody tried this in XQuery or if I am so foolish (not yet but > give me time) would I be the courageous <culturalReference> > http://www.youtube.com/watch?v=ik8JT2S-kBE</culturalReference> early > adopter. > >>> > > >>> > > >>> > _______________________________________________ > >>> > [email protected] > >>> > http://x-query.com/mailman/listinfo/talk > >> > >> > >> > >> _______________________________________________ > >> [email protected] > >> http://x-query.com/mailman/listinfo/talk > > > > > > > > > > > _______________________________________________ > > [email protected] > > http://x-query.com/mailman/listinfo/talk > > >
_______________________________________________ [email protected] http://x-query.com/mailman/listinfo/talk
