Re: [Maxima-discuss] rules and patterns for non-commuting multiplication

 Re: [Maxima-discuss] rules and patterns for non-commuting multiplication From: Richard Fateman - 2014-02-28 16:50:50 ```This is probably NOT what you want, which is to learn about rules. But I was thinking that the if the processing is of actual computational interest, it can be done so much faster (different order of processing) I should think about just writing it down. I wrote a simple version in lisp, and it is included below. It works for any number of (single-letter) names and uses alphabetical order. I have perhaps made some other unwarranted assumptions, and I assume that Maxima will simplify some remaining items, and sort the results. but see code. I have not tested this much. (run '((mnctimes) \$a \$b \$b \$a \$c )) returns ... ((mplus) ((mtimes) 1 ((mnctimes simp) \$b)) ((mtimes) 1 ((mnctimes simp) \$c \$b \$b \$a \$a)) ((mtimes) 1 ((mnctimes simp) \$a)) ((mtimes) 1 ((mnctimes simp) \$c \$b \$a)) ((mtimes) 2 ((mnctimes simp) \$b \$b \$a)) ((mtimes) 2 ((mnctimes simp) \$b \$a \$a))) i.e. abbac -> b+cbbaa + a + cba+2bba+2baa. #|Zeitlinie@... asks Let's say I have two atoms a and b, they can be non-commutatively multiplied, and should satisfy the rule a.b = b.a + 1 now it is (far too) simple to tellsimp(a.b,b.a+1); But this will only apply the rule to a.b The generic case of any product, with any number and order of a and b, is not expanded according to a.b = b.a + 1. How would one do this? ... Actually I'd be very surprised if this would have never been implemented by 'someone', because it is a stripped down version of something that many-body physicist like to do when they 'normal' order bosons (in my case its just single boson). |# #| Fairly easy and hugely hugely faster to do this without patterns. 1. Convert from a.b.c... to array or string "abc..." 2. Consider 2 hash tables indexed by strings. processing and done. 3. Strings in which the characters are in the proper order are in the table "done" with a count of how many times they were inserted. The empty string is in order. 4. Strings in the processing table are tested: a. If s in proper order, it is removed and the entry in the done table is incremented. If no entry, it is inserted with count 1. b. for each string s in processing, let n be the location of the first pair out of order, s[n] and s[n+1]. i. Insert in the processing table the string s with s[n],s[n+1] reversed. ii. Also insert the string with s[n..n+1] removed. That is, shorter by 2. iii. Finally, remove the string s from the table. 5. If all strings removed from processing table, go through the done table and convert to form you would like. Let the Maxima simplifier simplify 1*b to b etc. |# (defun mnc2string(r) ;; assume a.b.c.a.b . Single chars seems to be OK? ;; ((mnctimes simp) \$a \$b \$c ...) (let ((len (length (cdr r))) (inits (mapcar #'(lambda(c)(aref (symbol-name c) 1)) (cdr r )))) (make-array len :element-type 'character :initial-contents inits))) ;; (mnc2string '((mnctimes) \$a \$b \$foo \$a \$g)) ;; returns "abfag" (defun string2mnc(s) (let ((result nil)) (map nil #'(lambda(c) (push (intern(concatenate 'string '(#\\$)(list c))) result)) s) (cons '(mnctimes simp)(nreverse result)))) ;;(string2mnc "abcd") returns ((mnctimes simp) \$a \$b \$c \$d) ;; (unorder s) returns integer n if s[n] and s[n+1] are out of order. ;; nil if everything is in order. (defun unorder(s) (let ((h (length s))) (cond ((= h 0) nil) ;; empty string is in order (t (do ((i 0 (1+ i)) (j 1 (1+ j))) ((= j h) nil) (if (char-lessp (aref s i)(aref s j))(return i))))))) ;;(unorder "cbab") is 2 ;; (unorder "cba") is nil (defun removepair(s n) ;; remove items n, n+1 from string s of length (hash-table-count processing) 0) (maphash #'(lambda(key val) (let ((n (unorder key))) (cond ((null n) (setf (gethash key done) (+ val (gethash key done 0))) (remhash key processing)) (t (let ((rem (removepair key n)) (rev (reversepair key n))) (setf (gethash rem processing) (1+(gethash rem processing 0))) (setf (gethash rev processing) (1+(gethash rev processing 0))) (remhash key processing)))))) processing)) (maphash #'(lambda (key val) (push (list '(mtimes) val (string2mnc key)) res)) done) (cons '(mplus) res))) ```

 [Maxima-discuss] rules and patterns for non-commuting multiplication From: Mark - 2014-02-20 12:31:55 ```Let's say I have two atoms a and b, they can be non-commutatively multiplied, and should satisfy the rule a.b = b.a + 1 now it is (far too) simple to tellsimp(a.b,b.a+1); But this will only apply the rule to a.b The generic case of any product, with any number and order of a and b, is not expanded according to a.b = b.a + 1. How would one do this? -M ```
 Re: [Maxima-discuss] rules and patterns for non-commuting multiplication From: Richard Fateman - 2014-02-20 15:51:14 ```On 2/20/2014 4:31 AM, Mark wrote: > Let's say I have two atoms a and b, they can be non-commutatively > multiplied, and should satisfy the rule > > a.b = b.a + 1 > > now it is (far too) simple to > > tellsimp(a.b,b.a+1); > > But this will only apply the rule to > a.b > The generic case of any product, with any number and order of a and b, > is not expanded according to a.b = b.a + 1. There are several issues. You have not specified what to do with anything but a and b specifically in a dot-product of just the two of them. As you realize. But you haven't specified what you mean by "according to". Here are some thoughts. You might find it useful to transform a.b.c.d which has all 4 operands under a single operator mnctimes, internally into a binary-dot version so that rules for 2-terms only can cover the concept. That is dot2(a, dot2(b, dot2(c,d))) This can be done with a single rule, as it happens: matchdeclare([at,bt],true); tellsimp(at.bt, dot2(at,bt)); or you might want to use defrule so as to not mess up the "." for later use. Now at least you can try to specify the rules for a simpler task involving dot2. .............. You may also be trying to re-invent something that is already in Maxima (one of the tensor packages, or maybe linear algebra.). ....................... Anyway Maxima is not equipped to guess what a.b.c should do. I don't know what the answer is, though maybe I can guess. is a.b.c -> (b.a+1).c or a.(c.b+1) and is that expanded? if you expand, repeatedly, then I suspect you intend to end up, either way with c.b.a+a+b+c . Why not just compute that form directly? ............... For ordering you might find the function orderlessp useful. or you might make the substitution a->r[1], b-> r[2], c->r[3] in which case the index shows the order. ............... And then also you might need dot2(number,a) = dot2(a,number) is just a. Using 0 and 1 for identities this way is a kind of mathematical pun. Do you want to follow what Maxima does, or something else. For a final pass, change r[2]-> b and dot2(a,b) to a.b for display. ........... (repeating...) I suspect that someone else has already done all this for the same set of rules you have in mind, and it is in the share directory on your computer. ```
 Re: [Maxima-discuss] rules and patterns for non-commuting multiplication From: Mark - 2014-02-20 18:49:56 ```On 02/20/2014 04:51 PM, Richard Fateman wrote: > On 2/20/2014 4:31 AM, Mark wrote: >> Let's say I have two atoms a and b, they can be non-commutatively >> multiplied, and should satisfy the rule >> ...... >> The generic case of any product, with any number and order of a and b, >> is not expanded according to a.b = b.a + 1. > There are several issues. You have not specified what to do with > anything but a and b > specifically in a dot-product of just the two of them. As you realize. > But you haven't > specified what you mean by "according to". Just before trying to see if your input helps let me clarify this: There is some product, say: a.b.a.a.b.a.b For any of such product, there is one and only one final answer for 'commuting all b to the left' using the rule. Like so: a.b.a.a.b.a.b = a.b.a.a.b.(b.a+1) = a.b.a.a.b.b.a + a.b.a.a.b = a.b.a.(b.a+1).b.a + (b.a+1).a.a.b = a.b.a.b.a.b.a + a.b.a.b.a + b.a.a.a.b + a.a.b = .......and so on, until all bs are left in each addend > ..... snip ..... Still have to read that > I suspect that someone else has already done all this for the same > set of rules you have in mind, and it is in the share directory on > your computer. Actually I'd be very surprised if this would have never been implemented by 'someone', because it is a stripped down version of something that many-body physicist like to do when they 'normal' order bosons (in my case its just single boson). My question is not about reinventing the wheel, but about getting some understanding of pattern matching in Maxima. So if you would know a *.mac file for exactly this case that I could look at, I'd be interested. -M ```
 Re: [Maxima-discuss] rules and patterns for non-commuting multiplication From: Richard Fateman - 2014-02-28 16:50:50 ```This is probably NOT what you want, which is to learn about rules. But I was thinking that the if the processing is of actual computational interest, it can be done so much faster (different order of processing) I should think about just writing it down. I wrote a simple version in lisp, and it is included below. It works for any number of (single-letter) names and uses alphabetical order. I have perhaps made some other unwarranted assumptions, and I assume that Maxima will simplify some remaining items, and sort the results. but see code. I have not tested this much. (run '((mnctimes) \$a \$b \$b \$a \$c )) returns ... ((mplus) ((mtimes) 1 ((mnctimes simp) \$b)) ((mtimes) 1 ((mnctimes simp) \$c \$b \$b \$a \$a)) ((mtimes) 1 ((mnctimes simp) \$a)) ((mtimes) 1 ((mnctimes simp) \$c \$b \$a)) ((mtimes) 2 ((mnctimes simp) \$b \$b \$a)) ((mtimes) 2 ((mnctimes simp) \$b \$a \$a))) i.e. abbac -> b+cbbaa + a + cba+2bba+2baa. #|Zeitlinie@... asks Let's say I have two atoms a and b, they can be non-commutatively multiplied, and should satisfy the rule a.b = b.a + 1 now it is (far too) simple to tellsimp(a.b,b.a+1); But this will only apply the rule to a.b The generic case of any product, with any number and order of a and b, is not expanded according to a.b = b.a + 1. How would one do this? ... Actually I'd be very surprised if this would have never been implemented by 'someone', because it is a stripped down version of something that many-body physicist like to do when they 'normal' order bosons (in my case its just single boson). |# #| Fairly easy and hugely hugely faster to do this without patterns. 1. Convert from a.b.c... to array or string "abc..." 2. Consider 2 hash tables indexed by strings. processing and done. 3. Strings in which the characters are in the proper order are in the table "done" with a count of how many times they were inserted. The empty string is in order. 4. Strings in the processing table are tested: a. If s in proper order, it is removed and the entry in the done table is incremented. If no entry, it is inserted with count 1. b. for each string s in processing, let n be the location of the first pair out of order, s[n] and s[n+1]. i. Insert in the processing table the string s with s[n],s[n+1] reversed. ii. Also insert the string with s[n..n+1] removed. That is, shorter by 2. iii. Finally, remove the string s from the table. 5. If all strings removed from processing table, go through the done table and convert to form you would like. Let the Maxima simplifier simplify 1*b to b etc. |# (defun mnc2string(r) ;; assume a.b.c.a.b . Single chars seems to be OK? ;; ((mnctimes simp) \$a \$b \$c ...) (let ((len (length (cdr r))) (inits (mapcar #'(lambda(c)(aref (symbol-name c) 1)) (cdr r )))) (make-array len :element-type 'character :initial-contents inits))) ;; (mnc2string '((mnctimes) \$a \$b \$foo \$a \$g)) ;; returns "abfag" (defun string2mnc(s) (let ((result nil)) (map nil #'(lambda(c) (push (intern(concatenate 'string '(#\\$)(list c))) result)) s) (cons '(mnctimes simp)(nreverse result)))) ;;(string2mnc "abcd") returns ((mnctimes simp) \$a \$b \$c \$d) ;; (unorder s) returns integer n if s[n] and s[n+1] are out of order. ;; nil if everything is in order. (defun unorder(s) (let ((h (length s))) (cond ((= h 0) nil) ;; empty string is in order (t (do ((i 0 (1+ i)) (j 1 (1+ j))) ((= j h) nil) (if (char-lessp (aref s i)(aref s j))(return i))))))) ;;(unorder "cbab") is 2 ;; (unorder "cba") is nil (defun removepair(s n) ;; remove items n, n+1 from string s of length (hash-table-count processing) 0) (maphash #'(lambda(key val) (let ((n (unorder key))) (cond ((null n) (setf (gethash key done) (+ val (gethash key done 0))) (remhash key processing)) (t (let ((rem (removepair key n)) (rev (reversepair key n))) (setf (gethash rem processing) (1+(gethash rem processing 0))) (setf (gethash rev processing) (1+(gethash rev processing 0))) (remhash key processing)))))) processing)) (maphash #'(lambda (key val) (push (list '(mtimes) val (string2mnc key)) res)) done) (cons '(mplus) res))) ```
 Re: [Maxima-discuss] rules and patterns for non-commuting multiplication From: Robert Dodier - 2014-02-23 23:52:32 ```On 2014-02-20, Mark wrote: > Let's say I have two atoms a and b, they can be non-commutatively > multiplied, and should satisfy the rule > > a.b = b.a + 1 > > now it is (far too) simple to > > tellsimp(a.b,b.a+1); > > But this will only apply the rule to > a.b > The generic case of any product, with any number and order of a and b, > is not expanded according to a.b = b.a + 1. > > How would one do this? I think I figured it out (after several attempts of varying success). As you have observed, the problem is that Maxima won't match a pattern with 2 operands to an expression with more than 2. I've worked around that by regrouping any instance of a.b so that it matches (function FOO in the code). Also, I set a couple of global flags -- dotexptsimp=false so that products aren't rolled up into exponents and dotdistrib=true so that stuff.(b.a + 1) is expanded automatically. Also, sometimes 'expand' is needed at the end to convince Maxima to simplify stuff*(foo + bar). There's more that could be said but anyway let's just see some examples. load ("boson.mac"); a.b; => b . a + 1 a.a.b.b; => a . a . b . b apply1 (a.a.b.b, boson_rule); => b . b . a . a+2*(b . a+1)+2*b . a expand (apply1 (a.a.b.b, boson_rule)); => b . b . a . a+4*b . a+2 ev (%, dotexptsimp=true); => b^^2 . a^^2+4*b . a+2 /* http://arxiv.org/pdf/quant-ph/0507206.pdf example on p 8 */ expand (apply1 (a.b.a.a.b.a.a.b, boson_rule)); => b . b . b . a . a . a . a . a+9*b . b . a . a . a . a+18*b . a . a . a+6*a . a ev (%, dotexptsimp=true); => b^^3 . a^^5+9*b^^2 . a^^4+18*b . a^^3+6*a^^2 The main problem solved here is that Maxima needs encouragement to group n-ary operands by twos. It is plausible that functionality might be incorporated into automatically-generated rules -- I'll think about that. best Robert Dodier PS. \$ cat boson.mac dotexptsimp : false; dotdistrib : true; tellsimp (a . b, b . a + 1); matchdeclare (aa, lambda ([e], not atom(e) and op(e) = ".")); defrule (boson_rule, aa, apply (".", FOO (args (aa)))); FOO (l) := collect (for i thru length (l) do if i < length (l) and l[i] = 'a and l[i + 1] = 'b then (emit (a . b), i : i + 1) else emit (l[i])); collect (e) ::= buildq ([e], block([stuff : []], e, stuff)); emit (x) := push (x, stuff); push (xx, yy) ::= buildq ([xx, yy], yy : append (yy, [xx])); ```
 Re: [Maxima-discuss] rules and patterns for non-commuting multiplication From: Barton Willis - 2014-02-24 01:08:16 ```> Also, sometimes 'expand' is needed at the end to convince Maxima to simplify stuff*(foo + bar). Trick: define a simplifying object whose sole simplification is expansion: (%i2) load(simplifying)\$ (%i3) simp_expanded(e) := (e : expand(e), simpfuncall('expanded,e))\$ (%i4) simplifying('expanded,'simp_expanded)\$ (%i5) apply1(a.a.a.b.b.b, boson_rule); (%o5) b . b . b . a . a . a+2*(b . b . a . a+3*(b . a)+1)+2*(b . b . a . a+b . a)+5*(b . b . a . a)+4*(b . a+1)+6*(b . a) (%i6) apply1(expand(%),boson_rule); (%o6) b . b . b . a . a . a+9*(b . b . a . a)+18*(b . a)+6 (%i7) apply1(expand(%),boson_rule); (%o7) b . b . b . a . a . a+9*(b . b . a . a)+18*(b . a)+6 Using an expanded object, only one application to apply1 is needed :) (%i8) apply1 (expanded(a.a.a.b.b.b), boson_rule); (%o8) expanded(b . b . b . a . a . a+9*(b . b . a . a)+18*(b . a)+6) --Barton ```
 Re: [Maxima-discuss] rules and patterns for non-commuting multiplication From: Richard Fateman - 2014-03-03 01:11:18 ```The rule in Robert's boson.mac is used simply to detect the presence of a "." operator and the rest of the processing is not really doing any matching. This is a good approach, and should not decay into useless search heuristics. The code I wrote in lisp is essentially the replacement for the program foo. It is approximately 100X faster. I found a small bug in it, but after fixing it, it provides the same answer. It is also helpful to first set dotexptsimp:false at the beginning. The maxima code (in lisp) is in http://cs.berkeley.edu/~fateman/lisp/ncm.lisp so you would do something like dotexptsimp:false\$ load(" ... ncm.lisp"); ?run(a.a.a.b.b.b); ev(%,dotexptsimp=true); Undoubtedly my code could be made faster, e.g. by :lisp (compile-file "...") and then loading the compiled version and there are also other possibilities esp. if your lisp isn't so fast accessing character strings. My code works for any number of variables as long as they have single-letter names, not just "a" and "b". Have fun. On 2/23/2014 5:08 PM, Barton Willis wrote: >> Also, sometimes 'expand' is needed at the end to convince Maxima to simplify stuff*(foo + bar). > Trick: define a simplifying object whose sole simplification is expansion: > > (%i2) load(simplifying)\$ > (%i3) simp_expanded(e) := (e : expand(e), simpfuncall('expanded,e))\$ > (%i4) simplifying('expanded,'simp_expanded)\$ > > (%i5) apply1(a.a.a.b.b.b, boson_rule); > (%o5) b . b . b . a . a . a+2*(b . b . a . a+3*(b . a)+1)+2*(b . b . a . a+b . a)+5*(b . b . a . a)+4*(b . a+1)+6*(b . a) > > (%i6) apply1(expand(%),boson_rule); > (%o6) b . b . b . a . a . a+9*(b . b . a . a)+18*(b . a)+6 > > (%i7) apply1(expand(%),boson_rule); > (%o7) b . b . b . a . a . a+9*(b . b . a . a)+18*(b . a)+6 > > Using an expanded object, only one application to apply1 is needed :) > > (%i8) apply1 (expanded(a.a.a.b.b.b), boson_rule); > (%o8) expanded(b . b . b . a . a . a+9*(b . b . a . a)+18*(b . a)+6) > > --Barton > > > ------------------------------------------------------------------------------ > Flow-based real-time traffic analytics software. Cisco certified tool. > Monitor traffic, SLAs, QoS, Medianet, WAAS etc. with NetFlow Analyzer > Customize your own dashboards, set traffic alerts and generate reports. > Network behavioral analysis & security monitoring. All-in-one tool. > http://pubads.g.doubleclick.net/gampad/clk?id=126839071&iu=/4140/ostg.clktrk > _______________________________________________ > Maxima-discuss mailing list > Maxima-discuss@... > https://lists.sourceforge.net/lists/listinfo/maxima-discuss ```