$\newcommand{\defeq}{\mathrel{\mathop:}=}$

## 2007/04/21

### Bernstein Polynomial

The following true story is perhaps the best way to explain the distinction I have in mind. Some years ago I had just learned a mathematical theorem from which it followed that any two n \times n matrices A and B of integers have a "greatest common right divisor" D. This means that D is a right divisor of A and of B, i.e., A = A' D and B = B' D for some integer matrices A' and B', and that every common right divisor of A and B is a right divisor of D. So I wondered how to calculate the greatest common right divisor of two given matrices. A few days later I happened to be attending a conference where I met the mathematician H. B. Mann, and I felt that he would know how to solve this problem. I asked him and he did indeed know the correct answer; but it was a mathematician's answer, not a computer scientist's answer! He said, "Let R be the ring of of n \times n integer matrices; in this ring, the sum of two principal left ideals is principal, so let D be such that

RA + RB = RD.

Then D is the greatest common right divisor of A and B." This formula is certainly the simplest possible one; we need only eight symbols to write it down. And it relies on rigorously-proved theorems of mathematical algebra. But from the standpoint of a computer scientist, it is worthless, since it involves constructing the infinite sets RA and RB, taking their sum, then searrching through infinitely many matrices D until finding one for which this sum matches the infinite set RD.

Knuth 後來倒有找到解決這個問題的 "computer scientist's answer"。Bernstein polynomial 在圖學的 Bézier curve 上好像也有一些應用，according to Wikipedia。（然後才突然想到，Bernstein polynomial 的形式的確和 Bézier curve 有點像，都有二項式的痕跡 XD。）

--

Labels: