From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 18198 invoked by alias); 5 Oct 2009 23:00:01 -0000 Received: (qmail 18187 invoked by uid 22791); 5 Oct 2009 23:00:00 -0000 X-SWARE-Spam-Status: No, hits=-6.3 required=5.0 tests=AWL,BAYES_00,SPF_PASS X-Spam-Check-By: sourceware.org Received: from proofpoint3.lanl.gov (HELO proofpoint3.lanl.gov) (204.121.3.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 05 Oct 2009 22:59:56 +0000 Received: from mailrelay2.lanl.gov (mailrelay2.lanl.gov [128.165.4.103]) by proofpoint3.lanl.gov (8.14.3/8.14.3) with ESMTP id n95Mxplj005241 for ; Mon, 5 Oct 2009 16:59:53 -0600 Received: from alvie-mail.lanl.gov (alvie-mail.lanl.gov [128.165.4.110]) by mailrelay2.lanl.gov (Postfix) with ESMTP id 9387815CA91B for ; Mon, 5 Oct 2009 16:53:57 -0600 (MDT) Received: from localhost (localhost.localdomain [127.0.0.1]) by alvie-mail.lanl.gov (Postfix) with ESMTP id 920267D00A7 for ; Mon, 5 Oct 2009 16:53:57 -0600 (MDT) X-NIE-2-Virus-Scanner: amavisd-new at alvie-mail.lanl.gov Received: from [130.55.124.157] (manticore.lanl.gov [130.55.124.157]) by alvie-mail.lanl.gov (Postfix) with ESMTP id 791A37D00A5 for ; Mon, 5 Oct 2009 16:53:57 -0600 (MDT) Subject: Re: containers tentative design summary From: Gerard Jungman To: gsl-discuss@sourceware.org In-Reply-To: <7f1eaee30910050750l738876b1p41e6bd8ae5aa6d16@mail.gmail.com> References: <1254708349.18519.4.camel@ForbiddenPlanet> <7f1eaee30910050750l738876b1p41e6bd8ae5aa6d16@mail.gmail.com> Content-Type: text/plain Date: Mon, 05 Oct 2009 23:00:00 -0000 Message-Id: <1254783367.28192.98.camel@manticore.lanl.gov> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-Proofpoint-Virus-Version: vendor=fsecure engine=1.12.8161:2.4.5,1.2.40,4.0.166 definitions=2009-10-06_01:2009-09-29,2009-10-05,2009-10-05 signatures=0 Mailing-List: contact gsl-discuss-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gsl-discuss-owner@sourceware.org X-SW-Source: 2009-q4/txt/msg00003.txt.bz2 On Mon, 2009-10-05 at 10:50 -0400, James Bergstra wrote: > Two comments: > > I'm a bit rusty with my C structs... but you would need two distinct > static classes to have const and non-const data pointers for your view > right? Yes, sorry. I left that out. > Also, it sounds like writing code that will work for a tensor of any > rank (e.g. add two tensors together) might be either tedious or > impossible. I recognize that part of the problem is the lack of > templating and polymorphism, but it would at least be comforting to > see just how bad the situation is via a use case or two in the design > documentation. I (naively?) fear that to get good performance will > require a whole library of functions for even the most basic of > operations. > > gsl_marray_add_1_0( gsl_marray_1, double ); > gsl_marray_add_1_1( gsl_marray_1, gsl_marray_1); > gsl_marray_add_1_2( gsl_marray_1, gsl_marray_2); > gsl_marray_add_2_2(... ) > ... > > gsl_marray_sub_1_0( ... ) > > Maybe a system of macros could be designed to help here, but it sounds > like it will never be as easy as writing a couple of for-loops. First, I want to be sure that we distinguish the multi-array case from the vector/matrix/tensor case. Algebra for vectors and matrices is well-defined and already on place; we only need to re-write some wrappers, etc. It is handled by BLAS calls. As I mentioned, this places a constraint on matrices, that the fast traversals be of unit stride. It seems like we just have to live with that constraint, for the matrix type. Addition, subtraction, scaling of multi-arrays is not hard because it is only defined within the same rank. So there is only a linear complexity, and no combinatorial explosion in the interfaces, for these operations. Of course, there are issues of shape conformance at run-time, but that is also true for vectors and matrices. That leaves multi-array algebra as an open question. By algebra, I mean technically the "cross-rank" operations, which form some kind of general multi-linear algebra. Sounds pretty hairy, as you suspect. First Idea: In fact, none of these operations are required from the library. If you have a good (fast) indexing scheme, then the user can implement whatever they want. This is the boost solution; boost::multi_array has no support for algebra operations. So we just punt on this. This was my implicit choice in the design summary. Second Idea: Implement as much as seems reasonable, in a way which is equivalent to what a user would do, with some loops. I am not sure that efficiency is an issue, since I don't see how you could do better than some loops, in the general case. Higher efficiency can be obtained for the vector and matrix types, using a good BLAS, but then it should be clear that the vector and matrix types are what you want, and not the general multi-array types. Third Idea: Figure out a way to generate everything automatically. Hmmm. Not likely. And the interface explosion would be ridiculous. Finally, we come to tensors. As defined in the design summary, tensors are multi-index objects with the same dimension at each place. We definitely do want to support the usual tensor algebra operations: tensor product and contraction. The question seems to be: How much simplicity do we gain in going from the general multi-array case to the restricted tensor case? If the interfaces for doing the tensor stuff are no less complicated than the general case, then we might as well go back and solve it for general multi-arrays. In any case, I think multi-array support would be a good thing, even without multi-linear algebra. Fixing up vectors and matrices so that the view types make sense is also a good thing. These are mostly orthogonal tasks; I just want to get them both clear in my head so I understand the limited ways in which they will interact. Right now I think the interaction is limited to some light-weight conversion functions between them and a common slicing mechanism. Tensors are another mostly orthogonal task. Again, they will benefit from the generic slicing mechanism, and there will be some light-weight conversion functions. But we can solve the problems here as we come to them. Does this make sense? -- G. Jungman