Module: SyMath::Operation::Normalization

Includes:
SyMath::Operation
Included in:
Value
Defined in:
lib/symath/operation/normalization.rb

Instance Method Summary collapse

Methods included from SyMath::Operation

#iterate, #recurse

Instance Method Details

#combine_factors ⇒ Object

Return result of the two factors multiplied if it simplifies the expression. Returns (new_exp, sign, changed)



321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
 
# File 'lib/symath/operation/normalization.rb', line 321

def combine_factors
  if factor1.is_a?(SyMath::Product)
    f1 = factor1.factor2
  else
    f1 = factor1
  end
  f2 = factor2

  # Natural numbers are calculated
  if f1.is_number? and f2.is_number?
    return replace_combined_factors((f1.value*f2.value).to_m), 1, true
  end

  if f1.is_unit_quaternion? and f2.is_unit_quaternion?
    ret = f1.calc_unit_quaternions(f2)
    if ret.is_a?(SyMath::Minus)
      return replace_combined_factors(ret.argument), -1, true
    else
      return replace_combined_factors(ret), 1, true
    end
  end

  if f1.is_a?(SyMath::Power)
    base1 = f1.base
    exp1 = f1.exponent
  else
    base1 = f1
    exp1 = 1.to_m
  end

  if f2.is_a?(SyMath::Power)
    base2 = f2.base
    exp2 = f2.exponent
  else
    base2 = f2
    exp2 = 1.to_m
  end

  if base1 == base2
    if base1.type.is_subtype?('tensor') and
      base2.type.is_subtype?('tensor') and
      (exp1 + exp2).is_number? and
      (exp1 + exp2).value > 1
      return replace_combined_factors(0.to_m), 1, true
    end
    
    return replace_combined_factors(base1**(exp1 + exp2)), 1, true
  end
  
  return self, 1, false
end

#compare_factors_and_swap ⇒ Object

Compare first and second element in product. Swap if they can and should be swapped. Return (sign, changed).



384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
 
# File 'lib/symath/operation/normalization.rb', line 384

def compare_factors_and_swap()
  f1 = factor1.is_a?(SyMath::Product) ? factor1.factor2 : factor1
  f2 = factor2

  if !f1.type.is_subtype?(:linop) or !f2.type.is_subtype?(:linop)
    # Non-linear operator cannot be swapped
    return 1, false
  end

  if !f1.type.is_scalar? and f2.type.is_scalar?
    # Scalars always go before non-scalar linops
    swap_factors
    return 1, true
  end

  if (f1.type.is_vector? or f1.type.is_dform?) and
    (f2.type.is_vector? or f2.type.is_dform?)
    # Only order simple vectors. Don't order vector
    # expressions
    # FIXME: We could do that. If so, we must get the dimension
    # of the variable and swap sign only if dim(f1)*dim(f2) is
    # odd.
    if f1.is_a?(SyMath::Definition::Variable) and f2.is_a?(SyMath::Definition::Variable)
      # Order vector factors
      if f2 < f1
        swap_factors
        return -1, true
      else
        return 1, false
      end
    end
  end

  if f1.type.is_scalar? and f2.type.is_scalar?
    # Corner case. Order the imagninary unit above other scalars in order
    # to make it bubble up to the other quaternions.
    if f2 == :i
      return 1, false
    end

    if f1 == :i
      swap_factors
      return 1, true
    end

    # Normalize as power factors so all factors with the same base
    # end up at the same place and can be combined.
    f1 = f1.power(1) if !f1.is_a?(SyMath::Power)
    f2 = f2.power(1) if !f2.is_a?(SyMath::Power)

    # Order scalar factors
    if f2 < f1
      swap_factors
      return 1, true
    else
      return 1, false
    end
  end

  # FIXME: Order other commutative and anti-commutative operators
  return 1, false
end

#normalize ⇒ Object

This operation provides an expression object with the normalize() method which normalizes an expression:

equal arguments of a product are contracted to integer powers
arguments of a product are sorted

equal arguments of a sum (with subtractions) are contracted to integer
products arguments in a sum are sorted
subtractive elements are put after the additive elements

integer sums are calculated
integer products are calculated

fractions of integers are simplified as far as possible

The operation is repeated until the expression is no longer changed



24
25
26
27
28
29
30
 
# File 'lib/symath/operation/normalization.rb', line 24

def normalize()
  if self.is_a?(SyMath::Equation)
    return SyMath::Equation.new(args[0].normalize, args[1].normalize)
  end

  return iterate('normalize_single_pass')
end

#normalize_matrix ⇒ Object 



142
143
144
145
146
147
148
 
# File 'lib/symath/operation/normalization.rb', line 142

def normalize_matrix()
  data = (0..nrows - 1).map do |r|
    row(r).map { |e| e.normalize }
  end

  return SyMath::Matrix.new(data)
end

#normalize_power ⇒ Object 



134
135
136
137
138
139
140
 
# File 'lib/symath/operation/normalization.rb', line 134

def normalize_power()
  norm = base.normalize.power(exponent.normalize)
  e, sign, changed = norm.reduce_modulo_sign
  e *= -1 if sign == -1

  return e
end

#normalize_product ⇒ Object 



111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/symath/operation/normalization.rb', line 111

def normalize_product()
  # Flatten the expression and order it
  e = factors.map do |f|
    f = f.normalize
  end

  e = e.inject(:*)

  if e.is_prod_exp?
    e = e.order_product
  end

  if e.is_prod_exp?
    e = e.reduce_constant_factors
  end

  if !SyMath.setting(:fraction_exponent_form)
    e = e.product_on_fraction_form
  end

  return e
end

#normalize_single_pass ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/symath/operation/normalization.rb', line 32

def normalize_single_pass
  if is_sum_exp?
    return normalize_sum
  end

  if is_prod_exp?
    return normalize_product
  end

  if is_a?(SyMath::Power)
    return normalize_power
  end

  if is_a?(SyMath::Matrix)
    return normalize_matrix
  end

  if is_a?(SyMath::Definition::Operator) and !@exp.nil?
    @exp = @exp.normalize
  end

  return recurse('normalize', 'reduce')
end

#normalize_sum ⇒ Object 



56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/symath/operation/normalization.rb', line 56

def normalize_sum()
  # Get normalized terms
  terms = self.terms.map do |e|
    if e.is_a?(SyMath::Minus)
      e.argument.normalize.neg
    else
      e.normalize
    end
  end

  # Collect equal elements into integer products
  
  # Hash: product[vector part][scalar part]
  products = {}
  
  terms.each do |t|
    c = 1
    p = []

    t.factors.each do |f|
      if f == -1
        c *= -1
        next
      elsif f.is_number?
        c *= f.value
      else
        p.push f
      end
    end

    if products.key?(p)
      products[p] += c
    else
      products[p] = c
    end
  end

  terms2 = []
  products.keys.sort.each do |p|
    p.unshift products[p]

    p = p.inject(1.to_m, :*)
    
    if !SyMath.setting(:fraction_exponent_form)
      p = p.product_on_fraction_form
    end

    terms2.push p
  end

  ret = terms2.reverse.inject(:+)
  
  return ret
end

#order_product ⇒ Object

Order the factors first by type, then, for commutative and anti- commutative factors, by content using bubble sort:

sign * constant numbers * scalar factors * other factors

  • Commutative factors are swapped without changing sign.

  • Swapping anti-commutative factors changes the sign.

Constant numers are multiplied to a single coefficient Other factors are reduced if possible:

fundamental quaternions can always be reduced.
exterior algebra basis vectors can be reduced whenever
a double occurrence is found.



197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
 
# File 'lib/symath/operation/normalization.rb', line 197

def order_product()
  # Bubble sort factors. Reduce factors and combine thm whenever possible
  done = false
  sign = 1
  head = self

  while !done
    done = true

    ex = head
    prev = nil

    while ex.is_a?(SyMath::Product)
      if factor1.is_a?(SyMath::Product)
        f, sign2, changed = factor1.factor2.reduce_modulo_sign
        if changed
          self.factor1.factor2 = f
          done = false
        end
      else
        f, sign2, changed = factor1.reduce_modulo_sign
        if changed
          self.factor1 = f
          done = false
        end
      end

      sign *= sign2

      ex, sign2, changed = ex.combine_factors
      done = false if changed
      sign *= sign2

      # The product has been combined.
      if prev.nil?
        # No prev element. Replace head with ex
        head = ex
      else
        # Attach the combined expression onto the previous product
        # exp and continue
        prev.factor1 = ex
      end

      if !ex.is_a?(SyMath::Product)
        next
      end
      
      sign2, changed = ex.compare_factors_and_swap
      done = false if changed
      sign *= sign2

      prev = ex
      ex = ex.factor1
    end
  end

  if sign == -1
    return -head
  else
    return head
  end
end

#product_on_fraction_form ⇒ Object 



150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/symath/operation/normalization.rb', line 150

def product_on_fraction_form
  ret = []
  fact = 1.to_m
  divf = 1.to_m
  
  factors.each do |f|
    if f.type.is_scalar?
      if f.is_divisor_factor?
        divf *= f.base**f.exponent.argument
      else
        fact *= f
      end
    else
      if divf != 1
        fact = fact/divf
      end
      if fact != 1
        ret.push fact
      end

      fact = f
      divf = 1.to_m
    end
  end

  if divf != 1
    fact = fact/divf
  end
  if fact != 1
    ret.push fact
  end

  return ret.empty? ? 1.to_m : ret.inject(:*)
end

#reduce_constant_factors ⇒ Object

FIXME: Do the reduction in the combine_factors part. Reduce c and c**-1 by gdc. The expression is expected to be flattened and ordered so that the first argument is the constand and the second argument is the divisor constant.



264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
 
# File 'lib/symath/operation/normalization.rb', line 264

def reduce_constant_factors()
  c = nil
  dc = nil
  ret = []

  self.factors.each do |f|
    if dc.nil?
      if f.is_divisor_factor?
        if f.base.is_number?
          dc = f.base.value**f.exponent.argument.value
          next
        end
      end
    end

    if c.nil?
      if f.is_number?
        c = f.value
        next
      end
    end

    c = 1 if c.nil?
    dc = 1 if dc.nil?

    ret.push f
  end

  c = 1 if c.nil?
  dc = 1 if dc.nil?

  # First examine the coefficients
  if c == 0 and dc > 0
    return 0.to_m
  end

  if c > 0
    # Reduce coefficients by greatest common divisor
    gcd = c.gcd(dc)
    c /= gcd
    dc /= gcd
  end

  if dc != 1
    ret.unshift dc.to_m**-1
  end

  if c != 1
    ret.unshift c.to_m
  end

  return ret.inject(:*)
end

#replace_combined_factors(e) ⇒ Object

Replace factor1 and factor2 with e. Return new combined expression



374
375
376
377
378
379
380
 
# File 'lib/symath/operation/normalization.rb', line 374

def replace_combined_factors(e)
  if factor1.is_a?(SyMath::Product)
    return factor1.factor1*e
  else
    return e
  end
end

#swap_factors ⇒ Object

Swap first and second argument in product



448
449
450
451
452
453
454
455
456
457
 
# File 'lib/symath/operation/normalization.rb', line 448

def swap_factors()
  f2 = self.factor2
  if self.factor1.is_a?(SyMath::Product)
    self.factor2 = self.factor1.factor2
    self.factor1.factor2 = f2
  else
    self.factor2 = self.factor1
    self.factor1 = f2
  end
end