On Mon, 21 Feb 2005 10:05:47 +0200, Georg Wrede wrote:

> 
> 
> Norbert Nemec wrote:
>> Nice work, Knud! Examples always are the best way to test a design idea...
> ....
>>> I think we need some way to tell the vectorization engine about special tensors like delta() and anti() !
> 
> Are there some special problems to be expected with that?
> (I'm no vector guy.) As in, do delta(), anti() and such
> demand something very special from the compiler/language,
> or are they just functions that could be written in D
> right now? And still work with vectorization?

Yes, take the determinant expression
det=sum([i in 0..4,j in 0..4,k in 0..4,l in 0..4]
     (anti(i,j,k,l)*a[0,i]*a[1,j]*a[2,k]*a[3,l]));

for every anti() we got 1 addition and 4 multiplications.
Now anti(i,j,k,l) have 256 combinations and is zero on 232
so if the compiler knows how to optimize anti it would
save 232 additions and 928 multiplications
and just leaving 24 additions and 96 multiplications.

Georg Wrede schrieb:
> 
> 
> Norbert Nemec wrote:
> 
>> Nice work, Knud! Examples always are the best way to test a design idea...
> 
> ....
> 
>>> I think we need some way to tell the vectorization engine about special tensors like delta() and anti() !
> 
> 
> Are there some special problems to be expected with that?
> (I'm no vector guy.) As in, do delta(), anti() and such
> demand something very special from the compiler/language,
> or are they just functions that could be written in D
> right now? And still work with vectorization?

Both could be implemented as plain functions quite trivially. However, using them without optimization would be the killer. Just consider replacing.

	f(3)

by

	sum([i in 0..1000](f(i)*delta(i,3)))

which is equivalent to

	sum([i in 0..1000](f(i)*(i==3?1:0))

Generally, I believe the Kronecker-Delta and the Levi-Civita-Symbol are best left to the pen-and-paper mathematicians. On the paper, that kind of formalism really saves the day. In numerics, I cannot see yet, why it would be a good idea to use it.

On Mon, 21 Feb 2005 13:59:25 +0100, Norbert Nemec wrote:

> Georg Wrede schrieb:
>> 
>> 
>> Norbert Nemec wrote:
>> 
>>> Nice work, Knud! Examples always are the best way to test a design idea...
>> 
>> ....
>> 
>>>> I think we need some way to tell the vectorization engine about special tensors like delta() and anti() !
>> 
>> 
>> Are there some special problems to be expected with that?
>> (I'm no vector guy.) As in, do delta(), anti() and such
>> demand something very special from the compiler/language,
>> or are they just functions that could be written in D
>> right now? And still work with vectorization?
> 
> Both could be implemented as plain functions quite trivially. However, using them without optimization would be the killer. Just consider replacing.
> 
> 	f(3)
> 
> by
> 
> 	sum([i in 0..1000](f(i)*delta(i,3)))
> 
> which is equivalent to
> 
> 	sum([i in 0..1000](f(i)*(i==3?1:0))
> 
> Generally, I believe the Kronecker-Delta and the Levi-Civita-Symbol are best left to the pen-and-paper mathematicians. On the paper, that kind of formalism really saves the day. In numerics, I cannot see yet, why it would be a good idea to use it.

Well I see vectorization notation as 2 parts.
1) unordered loops like [i in 0..3,k in 0..4]
2) an element relation like r[i]=sum([j in 0..m](a[i,j]*v[j])

The Kronecker-delta is identity matrix (I) expressed as an element
relation.

I =[i in 0..n,j in 0..n](delta(i,j));

The Levi-Civita-Symbol (anti(i,j,k)) is the concept of anti-symmetry
expressed as an element relation.

You will see it in calculation of cross products, determinants and co-matrices in normal linear algebra.

But the difference is that they can be used in high dimensions as well.

You could try to write a vectorized expression for cross product, a co-matrix or determinant without anti() to see how that looks.

Knud Sørensen schrieb:
> Well I see vectorization notation as 2 parts.
> 1) unordered loops like [i in 0..3,k in 0..4]
> 2) an element relation like r[i]=sum([j in 0..m](a[i,j]*v[j])
> 
> The Kronecker-delta is identity matrix (I) expressed as an element
> relation.
> 
> I =[i in 0..n,j in 0..n](delta(i,j));
> 
> The Levi-Civita-Symbol (anti(i,j,k)) is the concept of anti-symmetry
> expressed as an element relation.
> 
> You will see it in calculation of cross products, determinants and
> co-matrices in normal linear algebra.
> 
> But the difference is that they can be used in high dimensions as well.
> 
> You could try to write a vectorized expression for cross product, a
> co-matrix or determinant without anti() to see how that looks.

I believe I understand pretty well what you say (just doing my PhD in theoretical physics, I have had my share of index-orgies on the paper and at the blackboard... :-)  )

Mathematically, the idea of "relations" makes perfect sense. Computationally, I don't know yet, whether the concept is really that helpful. I makes sense to allow mathematical notation, but my opinion is, that the language should not demand any deep intelligence from the compiler. Meaning: Even without optimization, the performance should be reasonable.

It might seem convenient to have 'anti' available and be able to take compact expressions directly from the textbook. However, optimizing the expressions takes a lot of intelligence from the compiler. And unless you know exactly what the compiler optimizes, you should rather not trust that it will do what you expect. So in the end, you'll probably be better of coding these operations by hand anyway.

For the cross-product, for example the following expression would give you a nice vectorized version:
	[i in 0..2](u[(i+1)%3] * v[(i+2)%3] - u[(i+2)%3] * v[(i+1)%3])

Maybe not as beautiful as the mathematical version, but then - we do not need to simplify it, but we want to crunch numbers.

In article <cv5jbl$ihb$1@digitaldaemon.com>, Norbert Nemec says...
>
>Georg Wrede schrieb:
>>> (Instead of having a syntax that implies an order and then saying "But the compiler is allowed to change the order", I would strongly prefer a syntax that differs substantially from sequential statements.)
>> 
>> So, immediately above you say "sequential statements". Does that include the
>> 
>>     c[i, k] = a[i,j] * b[j, k];
>> 
>> above?
>
>In a way, yes. What I mean is: C is a strictly sequential language. The programmer is used to the fact that commands are executed in order. (This is, what "sequential" means)
>
>If we want to extend this by constructions that break that strict sequentiality, the syntax should be sufficiently distinct.
>
>> My dream is that we can come up with something that "vector folks" would love, but that also does not look too scary or intractable to programmers used to "the C notation family", including D.
>
>True. This is my dream as well. Of course, vectorized expressions will never be the first thing to learn for a D newby. They are an advanced concept and people will be able to use D for years without touching it. Anyhow, it should of course fit in as smooth as possible.
>
>As I see it, people can go forth step by step:
>
>1) use D just like C
>2) start using arrays
>3) start using array expressions (simple to understand, but neither
>fully flexible nor extendable)
>4) start using vectorized expressions (more advanced, fully mixable with
>array expressions.
>
>To illustrate the last point, it should be clear that array expressions
>	int[] a,b,c;
>	[...]
>	c = a+b;
>can always be replaced by their equivalent vectorized expressions
>	int[] a,b,c;
>	[...]
>	assert(a.length == b.length)
>	c = [i in 0..a.length](a[i]+b[i]);

Just curious - in the examples above (and for the rest of what you have in mind Norbert), using array expressions wouldn't neccessarily preclude any of the compiler optimizations that are available for the equivalent vectorized expression, would it?

Or will there need to be an implied order of operations with what you have in mind for array expressions?

Thanks,

- Dave

Dave schrieb:
> In article <cv5jbl$ihb$1@digitaldaemon.com>, Norbert Nemec says...
> 
>>Georg Wrede schrieb:
>>
>>>>(Instead of having a syntax that implies an order and then saying "But the compiler is allowed to change the order", I would strongly prefer a syntax that differs substantially from sequential statements.)
>>>
>>>So, immediately above you say "sequential statements". Does that
>>>include the
>>>
>>>    c[i, k] = a[i,j] * b[j, k];
>>>
>>>above?
>>
>>In a way, yes. What I mean is: C is a strictly sequential language. The programmer is used to the fact that commands are executed in order. (This is, what "sequential" means)
>>
>>If we want to extend this by constructions that break that strict sequentiality, the syntax should be sufficiently distinct.
>>
>>
>>>My dream is that we can come up with something that "vector folks"
>>>would love, but that also does not look too scary or intractable
>>>to programmers used to "the C notation family", including D.
>>
>>True. This is my dream as well. Of course, vectorized expressions will never be the first thing to learn for a D newby. They are an advanced concept and people will be able to use D for years without touching it. Anyhow, it should of course fit in as smooth as possible.
>>
>>As I see it, people can go forth step by step:
>>
>>1) use D just like C
>>2) start using arrays
>>3) start using array expressions (simple to understand, but neither fully flexible nor extendable)
>>4) start using vectorized expressions (more advanced, fully mixable with array expressions.
>>
>>To illustrate the last point, it should be clear that array expressions
>>	int[] a,b,c;
>>	[...]
>>	c = a+b;
>>can always be replaced by their equivalent vectorized expressions
>>	int[] a,b,c;
>>	[...]
>>	assert(a.length == b.length)
>>	c = [i in 0..a.length](a[i]+b[i]);
> 
> 
> Just curious - in the examples above (and for the rest of what you have in mind
> Norbert), using array expressions wouldn't neccessarily preclude any of the
> compiler optimizations that are available for the equivalent vectorized
> expression, would it?

Array expressions are basically just a shorthand for vectorized expressions. They are simpler to type and to read, but they work only for the simple cases. Apart from details like the range checking, there is no internal difference between the two examples above. The compiler should be able to produce identical code from both. (Actually, I think, a compiler would even use the same internal representation for both.)

In general: if array operations are flexible enough for the problem you want to solve, fine for you. Vectorized expressions are really meant only for the trickier cases.

> Or will there need to be an implied order of operations with what you
> have in mind for array expressions?

I'm not sure that I understand your question. For array operations, it is obvious, that the order is irrelevant:
	c = a+b;
might be executed like
	for(int i=0;i<a.length;i++) c[i] = a[i]+b[i];
or
	for(int i=a.length-1;i>=0;i--) c[i] = a[i]+b[i];
or in any other wild order.

For vectorized expressions, it is not quite as obvious, since you cannot prohibit side-effects. You might write something like
	[i in 1..m](a[i] = 0.25*(a[i-1]+2*a[i]+a[i+1]))
and suddenly, the result depends on the order in which the vectorized expression is calculated.

Such expressions are *errors*! The whole point of vectorized expressions is that the order is not defined so that the compiler is free to choose the most efficient one. The compiler may not be able to detect errors like the one above. A good compiler will complain. A less intelligent one might produce unpredictable code. (A moderately smart one might at least warn you, if it cannot outrule the possibility of a order-dependency.)

In article <cvdjjc$pl6$1@digitaldaemon.com>, Norbert Nemec says...
>
>Dave schrieb:
>> In article <cv5jbl$ihb$1@digitaldaemon.com>, Norbert Nemec says...
>> 
>>>Georg Wrede schrieb:
>>>
>>>>>(Instead of having a syntax that implies an order and then saying "But the compiler is allowed to change the order", I would strongly prefer a syntax that differs substantially from sequential statements.)
>>>>
>>>>So, immediately above you say "sequential statements". Does that include the
>>>>
>>>>    c[i, k] = a[i,j] * b[j, k];
>>>>
>>>>above?
>>>
>>>In a way, yes. What I mean is: C is a strictly sequential language. The programmer is used to the fact that commands are executed in order. (This is, what "sequential" means)
>>>
>>>If we want to extend this by constructions that break that strict sequentiality, the syntax should be sufficiently distinct.
>>>
>>>
>>>>My dream is that we can come up with something that "vector folks" would love, but that also does not look too scary or intractable to programmers used to "the C notation family", including D.
>>>
>>>True. This is my dream as well. Of course, vectorized expressions will never be the first thing to learn for a D newby. They are an advanced concept and people will be able to use D for years without touching it. Anyhow, it should of course fit in as smooth as possible.
>>>
>>>As I see it, people can go forth step by step:
>>>
>>>1) use D just like C
>>>2) start using arrays
>>>3) start using array expressions (simple to understand, but neither
>>>fully flexible nor extendable)
>>>4) start using vectorized expressions (more advanced, fully mixable with
>>>array expressions.
>>>
>>>To illustrate the last point, it should be clear that array expressions
>>>	int[] a,b,c;
>>>	[...]
>>>	c = a+b;
>>>can always be replaced by their equivalent vectorized expressions
>>>	int[] a,b,c;
>>>	[...]
>>>	assert(a.length == b.length)
>>>	c = [i in 0..a.length](a[i]+b[i]);
>> 
>> 
>> Just curious - in the examples above (and for the rest of what you have in mind Norbert), using array expressions wouldn't neccessarily preclude any of the compiler optimizations that are available for the equivalent vectorized expression, would it?
>
>Array expressions are basically just a shorthand for vectorized expressions. They are simpler to type and to read, but they work only for the simple cases. Apart from details like the range checking, there is no internal difference between the two examples above. The compiler should be able to produce identical code from both. (Actually, I think, a compiler would even use the same internal representation for both.)
>
>In general: if array operations are flexible enough for the problem you want to solve, fine for you. Vectorized expressions are really meant only for the trickier cases.
>
> > Or will there need to be an implied order of operations with what you have in mind for array expressions?
>
>I'm not sure that I understand your question. For array operations, it
>is obvious, that the order is irrelevant:
>	c = a+b;
>might be executed like
>	for(int i=0;i<a.length;i++) c[i] = a[i]+b[i];
>or
>	for(int i=a.length-1;i>=0;i--) c[i] = a[i]+b[i];
>or in any other wild order.
>
>For vectorized expressions, it is not quite as obvious, since you cannot
>prohibit side-effects. You might write something like
>	[i in 1..m](a[i] = 0.25*(a[i-1]+2*a[i]+a[i+1]))
>and suddenly, the result depends on the order in which the vectorized
>expression is calculated.
>
>Such expressions are *errors*! The whole point of vectorized expressions is that the order is not defined so that the compiler is free to choose the most efficient one. The compiler may not be able to detect errors like the one above. A good compiler will complain. A less intelligent one might produce unpredictable code. (A moderately smart one might at least warn you, if it cannot outrule the possibility of a order-dependency.)

Right - just checking my understanding of what is being discussed.

Wrt to the question on the order of array expression operations, I was just checking that there would not (for some reason) be an implicit order on those as they are being discussed in this thread.

Thanks,
- Dave

On Mon, 21 Feb 2005 17:02:05 +0100, Norbert Nemec wrote:



> It might seem convenient to have 'anti' available and be able to take compact expressions directly from the textbook. However, optimizing the expressions takes a lot of intelligence from the compiler. And unless you know exactly what the compiler optimizes, you should rather not trust that it will do what you expect. So in the end, you'll probably be better of coding these operations by hand anyway.

I see your concern.


> For the cross-product, for example the following expression would give
> you a nice vectorized version:
> 	[i in 0..2](u[(i+1)%3] * v[(i+2)%3] - u[(i+2)%3] * v[(i+1)%3])

Nice, but hard to generalizes to more dimensions.

I got the idea that maybe we put anti-symmetry in to the sum function
and make a antisum function, but I need to think more about it to
make a concrete suggestion.

> Maybe not as beautiful as the mathematical version, but then - we do not need to simplify it, but we want to crunch numbers.

Yes, but we also have to make sure that we can crunch the right numbers ;-)

ps.) Here is a beautiful vectorized expression for the n-dimensional
determinant (using anti).
sum([id[n] in 0..n](anti(id[])*multiply([i in 0..n]a[i,id[i]]))));

Knud Sørensen schrieb:
>>For the cross-product, for example the following expression would give
>>you a nice vectorized version:
>>	[i in 0..2](u[(i+1)%3] * v[(i+2)%3] - u[(i+2)%3] * v[(i+1)%3])
> 
> 
> Nice, but hard to generalizes to more dimensions.

The cross-product as such is inherently 3-dimensional. In higher dimensions, there may be similar things (like outer products and similar creatures) but they cannot really be called "generalizations" of the cross product.

> I got the idea that maybe we put anti-symmetry in to the sum function and make a antisum function, but I need to think more about it to make a concrete suggestion. 

That might be the way to go. Still not sure yet, whether it is really essential for the language. Unless I see a really nice and clean proposal, I would suggest to wait until we there is some experience with vectorized expressions in general.

> ps.) Here is a beautiful vectorized expression for the n-dimensional
> determinant (using anti). sum([id[n] in 0..n](anti(id[])*multiply([i in 0..n]a[i,id[i]]))));

Don't know, yet, what to think about this syntax for n-dimensional sums. I would have to see and understand a general syntax proposal before making up my mind about it.

B.t.w.: The 'multiply' should rather be called 'product' (since it should go parallel with 'sum' and not with 'add').

On Tue, 22 Feb 2005 14:18:19 +0100, Norbert Nemec wrote:

> Knud Sørensen schrieb:
>>>For the cross-product, for example the following expression would give
>>>you a nice vectorized version:
>>>	[i in 0..2](u[(i+1)%3] * v[(i+2)%3] - u[(i+2)%3] * v[(i+1)%3])
>> 
>> 
>> Nice, but hard to generalizes to more dimensions.
> 
> The cross-product as such is inherently 3-dimensional. In higher dimensions, there may be similar things (like outer products and similar creatures) but they cannot really be called "generalizations" of the cross product.

I where referring to the way you use anti-symmetry,
but here is a generalization of cross-product to
n-1 n-vectors.
Let a[n-1,n] represented an array of n-1 n-vectors

v=[i in 0..n]sum([id[n-1] in 0..n]anti(i,id[])*product([k in
0..n-1]a[k,id[k]));

>> I got the idea that maybe we put anti-symmetry in to the sum function and make a antisum function, but I need to think more about it to make a concrete suggestion.

Another idea might be to allow advance slices/masking.
Let p_anti and n_anti be slices which represent the positive and negetive
part of the anti tensor.

p_anti(3) would return (0,1,2),(2,0,1)...

then
det= sum([id[n] in p_anti(n)](product([i in 0..n]a[i,id[i]])) - [id[n] in
n_anti(n)](product([i in 0..n]a[i,id[i]])));


> That might be the way to go. Still not sure yet, whether it is really essential for the language. Unless I see a really nice and clean proposal, I would suggest to wait until we there is some experience with vectorized expressions in general.

Right now we are just playing with the problem to see what we can learn.

>> ps.) Here is a beautiful vectorized expression for the n-dimensional
>> determinant (using anti).
>> sum([id[n] in 0..n](anti(id[])*multiply([i in 0..n]a[i,id[i]]))));
> 
> Don't know, yet, what to think about this syntax for n-dimensional sums. I would have to see and understand a general syntax proposal before making up my mind about it.

The important ting is that we have a syntax which can express this type of problem not that it uses this exact syntax.


> B.t.w.: The 'multiply' should rather be called 'product' (since it should go parallel with 'sum' and not with 'add').

agree.