On Fri, Oct 11, 2013 at 04:13:41PM -0700, Andrei Alexandrescu wrote:
> On 10/11/13 3:42 PM, H. S. Teoh wrote:
> >On Sat, Oct 12, 2013 at 12:36:08AM +0200, deadalnix wrote:
> >>First thing. I see std.linarg I have no clue whatsoever what it even may be about. Do we really want to have a standard lib with names that look like base64 encoded ?
> >
> >I picked it up immediately. It's an obvious abbreviation of "linear algebra".
> 
> Honestly I first thought it was "linear-time algorithms".
[...]

But I thought that was the province of std.algorithm?

BTW, are we going to split up std.algorithm anytime soon, now that we have package.d? Jonathan is already working on splitting up std.datetime into more manageable pieces, and it would be nice if std.algorithm can be broken up into saner pieces too. (The last time I brought it up a few people supported it, but I haven't had the time to do anything about it so far.)


T

-- 
The easy way is the wrong way, and the hard way is the stupid way. Pick one.

On Friday, 11 October 2013 at 23:13:34 UTC, Andrei Alexandrescu wrote:
> Honestly I first thought it was "linear-time algorithms".
>
> Andrei

I thought it was some kind of algae species.

Why not just call it std.algebra?

On Friday, 11 October 2013 at 23:24:00 UTC, Andrej Mitrovic wrote:
> On Friday, 11 October 2013 at 23:13:34 UTC, Andrei Alexandrescu wrote:
>> Honestly I first thought it was "linear-time algorithms".
>>
>> Andrei
>
> I thought it was some kind of algae species.
>
> Why not just call it std.algebra?

Because, amongst people who know, numerical linear algebra algorithms form their own little world of computing apart from what may be called 'algebra'. 'Algebra' could mean any number of things, like symbolic algebra, but the entire world of MATLAB/R programmers know exactly what linalg might be. Numerical linear algebra. See the reference text by Golub and Van Loan.

I would try to fit this module under some larger numeric or scientific computing hierarchy, but I don't see one in  D yet.

The Julia language is the competitor here, and it is already well ahead of D, but who knows how the race will end?

-- Brian

On Friday, 11 October 2013 at 16:10:21 UTC, FreeSlave wrote:
> There is "Matrices and linear algebra" module in wish list. Let's discuss its design. D is complicated language so it's difficult to choose the right way here. We need to find compromise between efficiency and convenient interface. I'm going to make some suggestions how this module should look like.
>

>
> Please, make your suggestions too.

Firstly, my opinion is, it shouldn't be in the std package.

Secondly, if it's not super highly performant, noone will use it. The highest performing linalg libraries implement the low level BLAS API or are vendor specific, like the Intel MKL. These are super optimized libraries where the asm code is hand optimized by specialists (GotoBLAS and the derived OpenBLAS for instance), and these will be *very* hard to beat. So much so that if BLAS isn't used as the engine, it's very unlikely that your library will be used for serious number crunching.

Built above BLAS, you can find a number of libraries that make using linear algebra more pleasant. One such library, currently the best IMHO is Armadillo C++. It has the very big advantage that it mimics Matlab functions. This feature is extremely useful, because scientists very often model their algorithms in Matlab before porting them to C++. This is what is done in the company I work for.

So the best I could suggest is to study the Armadillo C++ library and port it to D.

On Saturday, 12 October 2013 at 05:20:11 UTC, SomeDude wrote:
> On Friday, 11 October 2013 at 16:10:21 UTC, FreeSlave wrote:
>> There is "Matrices and linear algebra" module in wish list. Let's discuss its design. D is complicated language so it's difficult to choose the right way here. We need to find compromise between efficiency and convenient interface. I'm going to make some suggestions how this module should look like.
>>
>
>>
>> Please, make your suggestions too.
>
> Firstly, my opinion is, it shouldn't be in the std package.
>
> Secondly, if it's not super highly performant, noone will use it. The highest performing linalg libraries implement the low level BLAS API or are vendor specific, like the Intel MKL. These are super optimized libraries where the asm code is hand optimized by specialists (GotoBLAS and the derived OpenBLAS for instance), and these will be *very* hard to beat. So much so that if BLAS isn't used as the engine, it's very unlikely that your library will be used for serious number crunching.
>
> Built above BLAS, you can find a number of libraries that make using linear algebra more pleasant. One such library, currently the best IMHO is Armadillo C++. It has the very big advantage that it mimics Matlab functions. This feature is extremely useful, because scientists very often model their algorithms in Matlab before porting them to C++. This is what is done in the company I work for.
>
> So the best I could suggest is to study the Armadillo C++ library and port it to D.

For these cases we may let users to choose low-level backend if they need. High-level interface and default implementation are needed anyway.

I called it std.linalg because there is website http://www.linalg.org/ about C++ library for exact computational linear algebra. Also SciD has module scid.linalg. We can use std.linearalgebra or something else. Names are not really important now.

Ok, things are more clear now. Today I look what I can do.

On Saturday, 12 October 2013 at 06:24:58 UTC, FreeSlave wrote:
>
> For these cases we may let users to choose low-level backend if they need. High-level interface and default implementation are needed anyway.
>
> I called it std.linalg because there is website http://www.linalg.org/ about C++ library for exact computational linear algebra. Also SciD has module scid.linalg. We can use std.linearalgebra or something else. Names are not really important now.
>
> Ok, things are more clear now. Today I look what I can do.

There are litterally dozens of linear algebra packages: Eigen, Armadillo, Blitz++, IT++, etc.

I was not complaining about the linalg name, but about the fact that you want to make it a std subpackage. I contend that if you want to make it a std package, it must be nearly perfect, i.e better performing than ALL the other alternatives, even the C++ ones, and that it's really good as an API. Else it will be deprecated because someone will have made a better alternative.

Given the number of past tries, I consider this project is very likely doomed to failure. So no std please.

On Friday, 11 October 2013 at 22:36:09 UTC, deadalnix wrote:
> First thing. I see std.linarg I have no clue whatsoever what it even may be about. Do we really want to have a standard lib with names that look like base64 encoded ?

linalg is a pretty standard contraction of linear algebra. It's in common usage.

On Saturday, 12 October 2013 at 08:47:33 UTC, SomeDude wrote:
> On Saturday, 12 October 2013 at 06:24:58 UTC, FreeSlave wrote:
>>
>> For these cases we may let users to choose low-level backend if they need. High-level interface and default implementation are needed anyway.
>>
>> I called it std.linalg because there is website http://www.linalg.org/ about C++ library for exact computational linear algebra. Also SciD has module scid.linalg. We can use std.linearalgebra or something else. Names are not really important now.
>>
>> Ok, things are more clear now. Today I look what I can do.
>
> There are litterally dozens of linear algebra packages: Eigen, Armadillo, Blitz++, IT++, etc.
>
> I was not complaining about the linalg name, but about the fact that you want to make it a std subpackage. I contend that if you want to make it a std package, it must be nearly perfect, i.e better performing than ALL the other alternatives, even the C++ ones, and that it's really good as an API. Else it will be deprecated because someone will have made a better alternative.
>
> Given the number of past tries, I consider this project is very likely doomed to failure. So no std please.

It's not my idea to include this kind of module into std. I found it in wish list here http://wiki.dlang.org/Wish_list so I supposed community needs it and it should be discussed and designed, and then implemented by someone, not necessarily by me, though I can and will try to do it by myself. You're right, we should to learn existing solutions firstly and then make the best in D.

I'm with SomeDude: This project is doomed to failure from the get go, and under no circumstances should be put into std.

First, some background so this doesn't seem too harsh. Numerical linear algebra is easily the single oldest and most well-developed area of computing. Period. There's a huge history there, and if you don't know it then whatever you make won't be used and will be universally derided. Second, beyond the background of implementations is the theoretical background of what they're used for and how that influences the API.

You also have understand that linear algebra algorithms and data structures come in 3 major varieties: Dense, Sparse Direct, and Iterative methods. For just the theoretical background on these and associated floating point issues there is an absolute minimum of the material similar to what's covered in these two standard references:
Matrix Computations by Golub and Van Loan: http://www.amazon.com/Computations-Hopkins-Mathematical-Sciences-ebook/dp/B00BD2DVIC/ref=sr_1_6?ie=UTF8&qid=1381614419&sr=8-6&keywords=nick+higham

Accuracy and Stability of Numerical Algorithms by Nick Higham: http://www.amazon.com/Accuracy-Stability-Numerical-Algorithms-Nicholas/dp/0898715210/ref=sr_1_7?ie=UTF8&qid=1381614419&sr=8-7&keywords=nick+higham

The old, well-tested, and venerable BLAS and LAPACK APIs/packages are just for dense matrices. There are other variants for different kinds of parallelism. And notice there are differences in numerical linear algebra between instruction level parallelism (like SSE and AVX), shared memory, distributed memory, and coprocessors (like OpenCL or CUDA). In terms of popular existing implementations there are more recent packages like Magma (http://icl.utk.edu/magma/), PLASMA(http://icl.cs.utk.edu/plasma/), PETSc (http://www.mcs.anl.gov/petsc/), Trillinos (http://trilinos.sandia.gov/), or Elemental (http://libelemental.org/). The most popular sparse direct package, as far as I know, is SuiteSparse (http://www.cise.ufl.edu/research/sparse/SuiteSparse/), which is wrapped by Eigen (http://eigen.tuxfamily.org/index.php?title=Main_Page). Eigen is so popular in part because it does a good job of balancing expression template magic for dense matrices and wrapping/calling BLAS/LAPACK and SuiteSparse.

The very popular NumPy and SciPy packages are also basically wrappers around BLAS and LAPACK. There is also a scipy.sparse package, but its API differences are an ongoing headache.

All of which is to say this is a very deep area, the differences in algorithms and storage are sufficiently fundamental to make a unified API very difficult, and in any case the D community simply cannot commit to developing and maintaining such a library or commit to rolling in future developments from ongoing research in the area. This is exactly the sort of thing that should be a third-party extension, like in every other language, rather than in the standard library.


On Saturday, 12 October 2013 at 08:47:33 UTC, SomeDude wrote:
> On Saturday, 12 October 2013 at 06:24:58 UTC, FreeSlave wrote:
>>
>> For these cases we may let users to choose low-level backend if they need. High-level interface and default implementation are needed anyway.
>>
>> I called it std.linalg because there is website http://www.linalg.org/ about C++ library for exact computational linear algebra. Also SciD has module scid.linalg. We can use std.linearalgebra or something else. Names are not really important now.
>>
>> Ok, things are more clear now. Today I look what I can do.
>
> There are litterally dozens of linear algebra packages: Eigen, Armadillo, Blitz++, IT++, etc.
>
> I was not complaining about the linalg name, but about the fact that you want to make it a std subpackage. I contend that if you want to make it a std package, it must be nearly perfect, i.e better performing than ALL the other alternatives, even the C++ ones, and that it's really good as an API. Else it will be deprecated because someone will have made a better alternative.
>
> Given the number of past tries, I consider this project is very likely doomed to failure. So no std please.

On Friday, 11 October 2013 at 16:10:21 UTC, FreeSlave wrote:
> There is "Matrices and linear algebra" module in wish list. Let's discuss its design. D is complicated language so it's difficult to choose the right way here. We need to find compromise between efficiency and convenient interface. I'm going to make some suggestions how this module should look like.
>
> First of all, it should provide two templates for matrices. Let's call them StaticMatrix and DynamicMatrix. The first one has "templated" size and therefore may use static arrays and compile-time checks. It can be useful when the size is determined by our needs, for example, in graphics. DynamicMatrix has variable size, i.e. it should be created in heap. It can be useful in all other math areas.
>
> Both templates should support all floating point types and moreover user-defined (for example wrappers for GMP library and others).
>
> For efficiency in both cases matrices should use one-dimensional array for inner representation. But actually I'm not sure if matrices should support other container types besides standard D arrays. The good thing about one-dimensional arrays is that they can be easily exposed to foreign functions, for example, to C libraries and OpenGL. So we should take care about memory layout - at least row-major and column-major. I think it can be templated too.
>
> But another question arises - which "majority" should we use in interface? Interface should not depend on inner representation. All functions need unambiguity to avoid complication and repetition of design. Well, actually we can deal with different majority in interface - we can provide something like "asTransposed" adapter, that will be applied by functions if needed, but then we will force user to check majority of matrix interface, it's not very good approach.
>
> Sometimes user takes data from some other source and wants to avoid copying in Matrix construction, but she also wants to get matrix functionality. So we should provide "arrayAsMatrix" adapter, that can adopt one-dimensional and two-dimensional arrays making them feel like matrices. It definitely should not make copy of dynamic array, but I'm not sure about static.
>
> About operation overloading. It's quite clear about 'add' and 'subtruct' operations, but what's about product? Here I think all 'op'-functions should be 'element by element' operations. So we can use all other operations too without ambiguity. For actual matrix multiplication it can provide 'multiply' or 'product' function. It's similar to Maxima approach, besides Maxima uses dot notation for these needs.
>
> Transposition. I've already mentioned "asTransposed" adapter. It should be useful to make matrix feel like transposed without its copying. We also can implement 'transpose' and 'transposed' functions. The first one transposes matrix in place. It's actually not allowed for non-square StaticMatrix since we can't change the size of this type of matrices at runtime. The second one returns copy so it's applicable in all cases. Actually I'm not sure should these functions be member functions or not.
>
> Invertible matrix. It must not be allowed for square StaticMatrix. DynamicMatrix may make checks at runtime. Same as for transposition we can implement 'invert' to invert in place and 'inverted' to make copy. There is issue here - what should we do when determinant is 0? I believe the best approach here is to throw exception since if user needs invertible matrix it's definitely exception when it can't be calculated.
>
> Please, make your suggestions too.

I'd like to echo some of the points made by CJS.

Rolling your own linear algebra (for anything other than very small matrices) is an exercise in futility unless you are prepared to become a world-class expert in what is an incredibly mature and detailed field.

Clever wrapping of industry standard libraries is the way to go.

I would love to see this https://github.com/cristicbz/scid taken further, which was a fork of scid that used clever magic to reduce matrix expressions to an semi-optimal set of blas calls. It doesn't appear to have got much love in recent times.