Commutativity is good in addition to associativity because then you can use Σ
Structure preservation in a morphism φ (aka φ(xy)=φ(x)φ(y)) is good because then if φ follows from the context, you can replace all of “φ(xyz)” and “φ(xy)φ(z)” and “φ(x)φ(yz)” with “xyz”
Bijectivity in a function f is good because then for any equation it is an equivalent transformation to apply f to both sides
Monotonicity in a function f is good because then you can apply it to both sides of an inequality
Huh, you’re right. That’s too bad, “well-definedness & injectivity” doesn’t flow so well, and I don’t see what comparable property surjectivity is good for.
Another thing that you can do when folding associative operations over a sequence is re-parenthesize them in a way that makes them more efficient to compute.
For example, if A is a 1x1000 vector, B is a 1000x1000 square matrix, and C is a 1000x1 vector, (AB)(BC) takes less time and space to compute than A(BB)C since the intermediate 1000x1000 BB needs to be stored explicitly in the latter.
In the following python snippet, the computation of A(BB)C takes around 3/4ths of a second, while (AB)(BC) takes a handful of milliseconds.
from time import time
from numpy.random import random
A = random((1, 1000))
B = random((1000, 1000))
C = random((1000, 1))
a0 = time(); print(A.dot(B.dot(B)).dot(C)); a1 = time(); print(a1 - a0)
b0 = time(); print(A.dot(B).dot(B.dot(C))); b1 = time(); print(b1 - b0)
(Ironically, the values can be slightly different since floating point multiplication and addition aren’t associative, unlike the corresponding operations over reals.)
Along the same lines, folds of associative operations over a sequence can be parallelized by parenthesizing the sequence as a balanced binary tree and evaluating the instances of the operation on separate nodes.
It works, but it’s self-certified, so your browser is probably blocking it. You can add an exception if you’d like, but I should have it fixed “soon” (3rd party certification can be gotten for free, I just need to get around to it).
In the same vein:
Commutativity is good in addition to associativity because then you can use Σ
Structure preservation in a morphism φ (aka φ(xy)=φ(x)φ(y)) is good because then if φ follows from the context, you can replace all of “φ(xyz)” and “φ(xy)φ(z)” and “φ(x)φ(yz)” with “xyz”
Bijectivity in a function f is good because then for any equation it is an equivalent transformation to apply f to both sides
Monotonicity in a function f is good because then you can apply it to both sides of an inequality
Don’t you just need injectivity here?
Huh, you’re right. That’s too bad, “well-definedness & injectivity” doesn’t flow so well, and I don’t see what comparable property surjectivity is good for.
Good stuff, thanks for your comment!
Another thing that you can do when folding associative operations over a sequence is re-parenthesize them in a way that makes them more efficient to compute.
For example, if A is a 1x1000 vector, B is a 1000x1000 square matrix, and C is a 1000x1 vector, (AB)(BC) takes less time and space to compute than A(BB)C since the intermediate 1000x1000 BB needs to be stored explicitly in the latter.
In the following python snippet, the computation of A(BB)C takes around 3/4ths of a second, while (AB)(BC) takes a handful of milliseconds.
(Ironically, the values can be slightly different since floating point multiplication and addition aren’t associative, unlike the corresponding operations over reals.)
Along the same lines, folds of associative operations over a sequence can be parallelized by parenthesizing the sequence as a balanced binary tree and evaluating the instances of the operation on separate nodes.
The website has internal links prefixed with https but the site doesn’t work with https.
It works, but it’s self-certified, so your browser is probably blocking it. You can add an exception if you’d like, but I should have it fixed “soon” (3rd party certification can be gotten for free, I just need to get around to it).
Edit: I have done this now.