de Boor–Golub Algorithm

The de Boor–Golub algorithm (BG) offers a third, numerically elegant route from the parallel Foster ladder to the series Cauer ladder. Unlike long-division, Khatwani, or Sobhy, BG works directly with the poles and weights of the Foster impedance and never manipulates high-order polynomials explicitly. The version given here follows Parthasarathy & Feldman, with the algebra simplified for network identification by deconvolution (NID).

Two equivalent forms of the impedance

  • S-fraction (Cauer ladder with alternating thermal capacitances \(k_{1},k_{3},\dots\) and resistances \(k_{2},k_{4},\dots\)):

    (88)\[Z(s)= \cfrac{1}{ k_{1}s+\cfrac{1}{ k_{2}+\cfrac{1}{ k_{3}s+\dots+\cfrac{1}{k_{2N+1}s}}}}\]

    See also the J-fraction to S-fraction conversion in J-fraction Route to the Cauer Ladder.

  • Pole–zero product

    (89)\[Z(s)= \frac{1}{k_{1}}\; \frac{\displaystyle\prod_{k=1}^{N}\bigl(1+s/z_{k}\bigr)} {\displaystyle\prod_{k=1}^{N+1}\bigl(1+s/s_{k}\bigr)} \;=\; \frac{1}{k_{1}}\, \frac{A_{N}(s)}{B_{N+1}(s)}\]

    where the poles lie at \(-s_{1},\dots,-s_{N+1}\) and the zeros at \(-z_{1},\dots,-z_{N}\). For details on the pole-zero representation in the Foster network, see From Spectrum to Foster Network.

Recurrence relation

Comparing (88) and (89) yields a three-term recurrence for \(B_{n}(s)\):

(90)\[\begin{split}\begin{aligned} B_{1}(s)&=(s+\lambda_{0})B_{0}(s),\\ B_{n}(s)&=(s+\lambda_{n-1}+\mu_{n-1})B_{n-1}(s) -\lambda_{n-2}\mu_{n-1}B_{n-2}(s), && n=2,\dots,N,\\ B_{N+1}(s)&=(s+\mu_{N})B_{N}(s)-\lambda_{N-1}\mu_{N}B_{N-1}(s). \end{aligned}\end{split}\]

The unknown scalars \(\lambda_{n}\) and \(\mu_{n}\) are determined on the fly by the scalar products that fix \(\lambda_{n}\) and \(\mu_{n}\).

Define the weighted inner products

(91)\[\begin{aligned} \langle B_{n},B_{n}\rangle &=\sum_{k=0}^{N} B_{n}^{2}(s_{k})\,w_{0k} \end{aligned}\]
(92)\[\begin{aligned} \langle sB_{n},B_{n}\rangle &=\sum_{k=0}^{N} s_{k}\,B_{n}^{2}(s_{k})\,w_{0k} \end{aligned}\]

Then:

(93)\[\begin{aligned} \lambda_{n-1}\mu_{n}&=\frac{\langle B_{n},B_{n}\rangle} {\langle B_{n-1},B_{n-1}\rangle}, && n=1,\dots,N \end{aligned}\,.\]
(94)\[\begin{aligned} \lambda_{n}+\mu_{n}&=\frac{\langle sB_{n},B_{n}\rangle} {\langle B_{n},B_{n}\rangle}, && n=1,\dots,N \end{aligned}\]

For a general pole–zero form the weights \(w_{0k}\) are

(95)\[w_{0k}=\frac{A_{N}(s_{k})}{B_{N+1}'(s_{k})} = \frac{\displaystyle\prod_{i=1}^{N}(z_{i}-s_{k})} {\displaystyle\prod_{i=0,i\ne k}^{N}(s_{i}-s_{k})}\,.\]

With the Foster sum

(96)\[Z(s)=\sum_{k=0}^{N}\frac{w_{0k}}{s+s_{k}}\]

the poles are \(s_{k}=1/(R_{k}C_{k})\) and the weights are simply \(w_{0k}=1/C_{k}\)— no zeros need to be computed.

Initial value Start the iteration with

(97)\[B_{0}(s)=1,\qquad \lambda_{0}=\frac{\sum_{k=0}^{N}s_{k}w_{0k}}{\sum_{k=0}^{N}w_{0k}}\]

Recovering the Cauer coefficients

Once all \(\lambda_{n},\mu_{n}\) are known the ladder elements follow:

(98)\[\begin{aligned} k_{1}&=\frac{1}{\sum_{k=0}^{N}w_{0k}}, & k_{2}&=\frac{1}{k_{1}\lambda_{0}} \end{aligned}\]
(99)\[\begin{aligned} k_{2n}&=\frac{\mu_{1}\mu_{2}\cdots\mu_{n-1}} {k_{1}\lambda_{0}\lambda_{1}\cdots\lambda_{n-1}}, & k_{2n+1}&=\frac{k_{1}\lambda_{0}\lambda_{1}\cdots\lambda_{n-1}} {\mu_{1}\mu_{2}\cdots\mu_{n}}, \quad n=1,\dots,N \end{aligned}\]

Here \(k_{2n}\) are thermal resistances, \(k_{2n+1}\) the thermal capacitances.

Algorithm summary

de Boor-Golub Algorithm for Foster-to-Cauer Conversion

Input: Foster poles \(s_k = 1/(R_k C_k)\) and weights \(w_{0k} = 1/C_k\)

Output: Cauer ladder elements \(\{k_1 \ldots k_{2N+1}\}\)

  1. \(\lambda_0 = \frac{\sum_{k=0}^{N}s_k w_{0k}}{\sum_{k=0}^{N}w_{0k}}\) (weighted mean of poles)

  2. \(B_0(s) = 1\)

  3. \(B_1(s) = s+\lambda_0\)

  4. for \(n = 1 \ldots N\) do

    1. Compute \(\langle B_n,B_n \rangle\) and \(\langle sB_n,B_n \rangle\)

    2. \(\lambda_{n-1} \mu_n = \frac{\langle B_n,B_n \rangle}{\langle B_{n-1},B_{n-1} \rangle}\)

    3. \(\lambda_n + \mu_n = \frac{\langle sB_n,B_n \rangle}{\langle B_n,B_n \rangle}\)

    4. Solve for \(\lambda_n, \mu_n\) from the two equations above

    5. \(B_{n+1}(s) = (s+\lambda_n+\mu_n)B_n(s) - \lambda_{n-1}\mu_n B_{n-1}(s)\)

  5. end for

  6. Compute Cauer elements:

    1. \(k_1 = \frac{1}{\sum_{k=0}^{N}w_{0k}}\)

    2. \(k_2 = \frac{1}{k_1\lambda_0}\)

    3. For \(n = 1 \ldots N\):

      1. \(k_{2n} = \frac{\mu_1\mu_2\cdots\mu_{n-1}}{k_1\lambda_0\lambda_1\cdots\lambda_{n-1}}\)

      2. \(k_{2n+1} = \frac{k_1\lambda_0\lambda_1\cdots\lambda_{n-1}}{\mu_1\mu_2\cdots\mu_n}\)