miniKanren and Multivariate Horner Schemes

8.7

miniKanren and Multivariate Horner Schemes

Brett Schreiber

Suppose we had a multivariate polynomial that we wanted to optimize to use as few operations as possible. Here is an example which starts with 6 multiplications and 5 additions, gets transformed by a greedy algorithm, and ends with 2 multiplications and 5 additions.

x^2 + xy + xz + xw + yw + zw
= x(x + y + z + w) + yw + zw		Factor out x from 4 of the monomials.
= x(x + y + z + w) + w(y + z)		Factor out w from 2 of the monomials.

This transformation results in a multivariate Horner scheme. Although useful in reducing multiplications, multivariate Horner schemes are not optimal. Here is a different transformation which results in 1 multiplication and 3 additions.

x^2 + xy + xz + xw + yw + zw

= (x + y + z)(x + w)

1 The greedy algorithm

Ceberio and Kreinovich (2003) describe a greedy algorithm for producing a multivariate Horner scheme, given a multivariate polynomial:

Find a variable that appears in the most monomials. Halt if no variable appears more than once.
Factor out that variable from the monomials it appears in.
Recur twice: once on the newly-factored monomials, and once on the monomials which were left alone.

Recall the Racket function rember, which removes the first matching element x from a list l:

(define (rember x l)
  (cond
    ((null? l) '())
    ((equal? x (car l)) (cdr l))
    (else (cons (car l) (rember x (cdr l))))))

Now I can translate the formula into Racket, which I will call horner-step.

(define (horner-step x M)
  (let* ((Mᵢ (filter (λ (Mₖ) (member x Mₖ)) M))
         (Mₒ (filter (λ (Mₖ) (not (member x Mₖ))) M))
         (Mᵣ (map (λ (Mₖ) (rember x Mₖ)) Mᵢ)))
    `(+ (* ,x (+ . ,Mᵣ))
        (+ . ,Mₒ))))

Suppose we had a function that, given a multivariate polynomial, returned all the variables within.

(define (all-variables P)
  (match P
    ('() '())
    (`(() . ,t) (all-variables t))
    (`((,a . ,d) . ,t) (let ((rec (all-variables `(,d . ,t))))
                         (if (member a rec) rec `(,a . ,rec))))))

(define (most-frequent-variable P)
  (max-by
   (lambda (var) (length (filter (lambda (M)
                                   (member var M)) P)))
   (all-variables P)))

(define (max-by f l)
  (match l
    ('() #f)
    (`(,a . ,d) (let ((x (max-by f d)))
                  (if (and x (> (f x) (f a)))
                      x
                      a)))))