Khatwani’s Method

Khatwani’s algorithm converts the rational driving-point impedance straight into the \(H_k,h_k\) continued fraction (Equation (65) of the J-fraction Route to the Cauer Ladder page). The scheme relies only on

The first \(2N\) Markov parameters (Maclaurin coefficients) of \(Z(s)\),
A fast polynomial inverse built by Newton doubling,
A triangular calculation table that yields \(H_i, h_i\).

Khatwani’s method requires arbitrary-precision floating-point arithmetic and for very large systems, precision limitations can become even more severe than in polynomial long division.

Prerequisites

Start from the rational form (same as Equation (63) earlier)

(70)\[Z(s)= \frac{\alpha_0+\alpha_1s+\dots+\alpha_{N-1}s^{N-1}} {\beta_0+\beta_1s+\dots+\beta_{N-1}s^{N-1}+\beta_N s^{N}} .\]

Markov parameters

Expand about \(s=\infty\) (equivalently \(t=1/s\to 0\)):

(71)\[Z(s)=\sum_{i=1}^{\infty}\frac{y_i}{s^{\,i}} =\sum_{i=1}^{\infty}y_i t^{\,i} .\]

Write \(Z(t)\) explicitly by dividing numerator and denominator by \(\beta_N\) and reversing the order of coefficients

(72)\[\begin{aligned} Z(t)&= \frac{ \gamma_1 t+\gamma_2 t^2+\dots+\gamma_{N-1}t^{N-1}+\gamma_N t^{N}} {1+\delta_1 t+\dots+\delta_{N-1}t^{N-1}+\delta_N t^{N}} , \end{aligned}\]

where the new coefficients are

(73)\[\gamma_i=\alpha_{N-i}/\beta_N , \qquad \delta_i=\beta_{N-i}/\beta_N .\]

The strategy to obtain the Markov parameters is to invert the denominator of (72) and multiply it with the numerator. In the following, an algorithm for polynomial inversion is described.

Polynomial inverse by Newton doubling

Let

(74)\[P(t)=1+\delta_1 t+\dots+\delta_N t^N .\]

We need \(Q(t)=P(t)^{-1}\) accurate up to degree \(2N\) so that \(Z(t)=Q(t)\,(\gamma_1 t+\dots+\gamma_N t^N)\) reproduces the first \(2N\) Markov parameters.

For any integer \(i\) we call \(Q_i(t)\) an \(i\)-degree inverse if

(75)\[P(t)\,Q_i(t)=1+\mathcal O\!\bigl(t^{\,i}\bigr) .\]

Set \(Q_1(t)=1\) . With

(76)\[E_i(t)=\frac{P(t)\,Q_i(t)-1}{t^{\,i}}\]

we obtain the doubling update

(77)\[\begin{split}\begin{aligned} Q_{2i}(t)&=Q_i(t)-t^{\,i}\,E_i(t)\,Q_i(t) ,\\ E_{2i}(t)&=-\bigl[E_i(t)\bigr]^{2} . \end{aligned}\end{split}\]

Iterate until the degree exceeds \(2N\); multiply \(Q_{2N}(t)\) with the numerator polynomial to read off the Markov parameters \(y_1,\,\dots,\,y_{2N}\) .

Triangular calculation table

Construct the matrix (only labelled entries shown)

(78)\[\begin{split}\begin{pmatrix} A_{1,1} \\[2pt] A_{2,1} & A_{2,2} & \dots & A_{2,j} & \dots & \dots & A_{2,2N}\\ A_{3,1} & A_{3,2} & \dots & A_{3,j} & \dots & A_{3,2N-2} &\\ A_{4,1} & A_{4,2} & \dots & \dots & A_{4,2N-4} & & \\[-2pt] \vdots & \vdots & \vdots & & & & \\ A_{N+1,1}&A_{N+1,2}& & & & & \\ \end{pmatrix}\end{split}\]

initialise \(A_{1,1}=1\) , \(A_{2,j}=y_j\) ;
fill rows \(j = 1\ldots 2N\) with

(79)\[A_{i,j}=A_{i-2,j+2}-H_{i-2}\,A_{i-1,j+2}-h_{i-2}\,A_{i-1,j+1} .\]

Row by row the first two entries give

(80)\[H_i=\frac{A_{i,1}}{A_{i+1,1}} ,\qquad h_i=\frac{A_{i,2}-H_i\,A_{i+1,2}}{A_{i+1,1}} , \qquad i=1,\dots,N .\]

These \(H_i , h_i\) coefficients complete the H–h fraction (Equation (65)) . Convert to the J-fraction via Equation (66) and finally to the Cauer S-fraction with the recurrence (69) described in J-fraction Route to the Cauer Ladder .