Improving erasure-resilient encoding/decoding by combining Cauchy and Hankel/Toeplitz matrix

structure

Victor Y. Pan^{∗} Mathematics and Computer Science Department Lehman College, CUNY, Bronx, NY 10468 internet: vpan@alpha.lehman.cuny.edu

Abstract

We combine Cauchy and Toeplitz/Hankel matrix structure to improve the estimated running time and memory space of the known practical schemes for erasure-resilient encoding/decoding. Both encoding and decoding stages can be performed in nearly linear time by involving polynomial interpolation and multipoint evaluation. Due to the large overhead constants of the asymptotically fast known algorithms for the latter tasks (particularly, for interpolation), the resulting encoding/decoding scheme is, however, considered practically inferior to the more straightforward quadratic time algorithms. We propose a new algorithm (with its three variations at the encoding stage) that substantially decreases the latter overhead constants at both encoding and decoding stages. At the encoding stage, the algorithm also yields acceleration by logarithmic factor – to reach the complexity level of FFT or polynomial multiplication. Our computations do not involve polynomial interpolation. Multipoint polynomial evaluation is kept local to only one substage of the decoding computations. Even if this substage is replaced by the known algorithms running in quadratic time, our improvements at the other stages makes our algorithm practically very promising. Technically, we achieve our progress by combining the Cauchy structure of the generator matrix with Hankel/Toeplitz matrix structure.

Key words: erasure-resilient encoding/decoding, Cauchy matrices, Hankel/Toeplitz matrices.

1 Introduction

The power of using matrix structure for encoding/decoding algorithms is well known but was not fully explored yet. In this paper we exploit such a power to improve the computations by the known scheme for erasure-resilient encoding/decoding, at both encoding and decoding stages of the computations.

The known approach reduces the encoding to Trummer’s celebrated problem (cf. [Go85], [PACLS98]) of multiplication of an (n − m) × m nonsingular Cauchy matrix C by a vector provided that m information packets and n − m redundant packets are sent through the communication channel and a total of n−m packets are erased. The decoding is reduced to solving a nonsingular linear system of k equations whose coefficient matrix is a submatrix of C and, therefore, is also a Cauchy matrix (cf. [MS77], [ABELS94], [WB94], [AEL95] on this approach). Applications of the fast algorithms of [Ge87] for Trummer’s problem and [Ga60] for solving a Cauchy linear system yield encoding/decoding at the computational cost O(E(ℓ)n/ℓ + I(k) + E(k)). Here and hereafter, ℓ = min{m, n − m}, and we write E(s) = O(M(s) log s), I(s) = O(M(s) log s), and M(s) = O((s log s) log log s) to denote the computational cost of the evaluation of a polynomial of degree s at s+1 points, interpolation to such a polynomial, and multiplication of two polynomials of degree s, respectively (cf. [BP94]). (We measure the computational cost in terms of the number of field operations involved and will refer to them as ops.)

∗Supported by NSF Grant CCR 9732206 and PSC-CUNY Award 669363

The overhead constants hidden in the above ”O” notation are quite large, however, particularly for the interpolation, and in practice the computation goes by more straightforward algorithms that involve O((n − m)m) and O(k^{2}) ops at the stages of encoding and decoding, respectively [BKKKLZ95].

We propose an alternative solution algorithm (with its three variations at the encoding stage), which better exploits the Cauchy structure involved. This enables us to avoid interpolation completely and to limit multipoint polynomial evaluation to the decoding stage. The encoding stage can be performed in O(M(ℓ)n/ℓ) ops (see section 5) or, alternatively, by using O(r)+2DF T (r) ops provided that r ≥ max{m, n−m} and the ground field allows us to perform the discrete Fourier transform at the r-th roots of 1 by using DFT(r) ops, which is O(r log r) if FFT can be applied (see section 9). At the stage of decoding it is sufficient to use O(E(k) + M(k)) ops. In all our estimates, at both encoding and decoding stages, we achieve substantial decrease of the overhead constants in the ”O” notation, versus the approach based on [Ga60] and [Ge87], and also save logarithmic factor in the time bound for encoding (cf. sections 6 and 10 and Remarks 7.1 and 8.1 in sections 7 and 8). All our computations are performed in linear space, of n words of memory at the encoding stage and from O(k) to n at the decoding stage. The new techniques demonstrate the potential power of the application of structured matrices to encoding/decoding and promise to be practically useful for the erasure–resilient encoding/decoding. The algorithm allows its further practical improvements by using the XOR’s computer words and tabulation (cf. [BKKKLZ95]). Our computations are reduced to polynomial nultiplication or FFT and, therefore, allow processor efficient parallel acceleration to yield the time bounds O(log m) and O(log^{2} k) at the encoding and decoding stages, respectively.

Due to the well known importance of Trummer’s problem [PACLS98], its solution proposed in section 7 may be of some independent interest.

Technically, our progress is achieved based on combining the Cauchy matrix structure, which ensures nonsingularity, with Hankel/Toeplitz structure, which supports additional theoretical and practical speed up of the computations.

We organize our paper as follows. After some definitions and preliminaries in the next section, we describe the basic encoding/decoding scheme in section 3, state our complexity estimates in section 4, and define the Hankel/Toeplitz matrix structure, which we combine with Cauchy structure, in section 5. In section 6 we study the inversion of a Cauchy matrix and summarize the resulting complexity estimates for our first algorithm, except for the stage of multiplication of the resulting inverse by a vector, which we cover in section 7. We describe two alternative algorithms in sections 8 and 9. Section 10 is left for a brief discussion.

Acknowledgement. The problem of improving the erasure-resilient encoding/decoding was brought to my attention by Marek Karpinski.

2 Definitions and some preliminary results

Fix two integers m and n, n > m > 0, a field F (say, GF [2] or GF [2^{L}]) and its n distinct elements s_{i}, i = 0, …, n − m − 1, and −t_{j}, j = 0, …, m − 1. Let I_{s} stand for the s × s identity matrix. Let s = (s_{i})_{i=0}^{n−m−1} ∈ F^{n−m}, t = (t_{j})_{j=0}^{m−1} ∈ F^{m}, u = (u_{i})_{i=0}^{p−1} ∈ F^{p}, v = (v_{i})_{i=0}^{q−1} ∈ F^{q} be some vectors of dimensions n − m, m, p and q, resp. For a vector r = (r_{i})_{i=0}^{k−1}, let V (r) = (r_{i}^{j})_{i,j=0}^{k−1} be a k × k Vandermonde matrix. For a vector or a matrix W, let W^{T} be its transpose. Let C = C(u, v) = (\frac{1}{u_{i}+v_{j}})_{i=0,j=0}^{p−1,q−1} be a p × q Cauchy matrix,

defined by two vectors u and v, and let G = G(u, v) = ( \begin{matrix}I_{m} \\ C(u, v) \end{matrix} ) ∈ F^{n×m} be the n × m

generator matrix. diag (u) = diag(u_{i})_{i=0}^{p−1} will be our notation for the p × p diagonal matrix with diagonal entries u_{0}, …, u_{p−1}; h_{u}(x) for the monic polynomial ∏_{i=0}^{p−1}(x − u_{i}) of degree p in x, h′_{u}(x) for its derivative in x, and card (S) for the cardinality of a set S.

For a vector v = (v_{j})_{j=0}^{q−1}, a matrix W = (w_{j,k})_{j=0,k=0}^{q−1,p−1}, and two subsets, J of the set {0, …, q − 1} and K of the set {0, …, p − 1}, let v_{J} be the subvector (v_{j})_{j∈J} of v and let W_{J,K} be the submatrix (w_{j,k})_{j∈J,k∈K} of W.

Hereafter, ”ops” stands for ”operations in the field F”, M(s) ops suffice to multiply modulo x^{s} a pair of polynomials in x,

M(s) = O((s log s) log log s),  (2.1)

H(k) ops suffice to compute the coefficients of the polynomial h_{u}(x) for a given vector u ∈ F^{k},

H(k) = O(M(k) log k),  (2.2)

E(k) ops suffice to evaluate a polynomial of degree at most k − 1 on a set of k points,

E(k) = O(M(k) log k),  (2.3)

and DF T (k) ops suffice to perform discrete Fourier transform on the set of the k-th roots of 1,

DF T (k) = O(k log k)  (2.4)

over a field that supports FFT (cf. e.g. [BP94] on the proofs of (2.1)-(2.4)).

Remark 2.1 In the field F = GF (2^{L}), the ops can be performed as operations with polynomials modulo a fixed irreducible polynomial of degree L or as XOR′s of computer words [MS77], [BKKKLZ95], XOR′s being the better choice in practice.

The minimum number of ops, required to multiply a fixed rectangular or square matrix W by a vector will be denoted by c_{W}.

Lemma 2.1 c_{V} ≤ c_{W} for any submatrix V of a matrix W.

Lemma 2.2 Let V be a k × ℓ block matrix with g × h blocks V (i, j), i = 0, …, k − 1; j = 0, …, ℓ − 1. Then c_{V} ≤ ∑_{i,j} c_{V (i,j)} + (ℓ − 1)gk.

We will also use the following results, the first and the third of which are obvious:

Lemma 2.3 c_{V (r)} = E(k).

Lemma 2.4 (cf. [PSD70]). c_{V^{T} (r)} = c_{V (r)}.

Lemma 2.5 If the field F supports FFT on the set of the k-th roots of 1 and if r is a vector of the k-th roots of 1, then C_{V (r)} = DF T (k).

Remark 2.2 By Lemma 2.1, the estimates of Lemmas 2.3-2.5 apply to all rectangular submatrices of V (r) and V^{T} (r).

Hereafter, we will write

ℓ = min{m, n − m}.  (2.5)

3 Erasure-resilient encoding/decoding scheme

The next scheme for erasure-resilient encoding/decoding involves a Cauchy matrix and relies on a Reed-Solomon systematic linear code with an m-packet message vector v and a generator matrix G = G(s, t) [MS77], [ABELS94], [WB94], [AEL95]. Stage 1 represents encoding, stages 2-5 decoding. Practically, the scheme is applied to several vectors v, which are processed successively or concurrently. Algorithm 3.1 (encoding/decoding).

1. (encoding m-packet message v). Compute the vector u = Gv.

2. Define a subset Q of card(Q) = n − m in the set {0, …, n − 1}, (Q indexes the n − m erased packets); its intersections, K, with the set {0, …, m − 1}, and P, with the set {m, …, n − 1}; the complements of these intersections, M = {0, …, m − 1} − K and J = {m, …, n − 1} − P; the subvectors u_{K} and u_{M} of u, and the square Cauchy matrix C_{J,K} ∈ F^{k×k} (a submatrix of C = C(s, t), for k = card(J) = card(K)).

3. Compute the matrix C̃ = C_{J,K}^{−1}.

4. Compute the vector v_{K} = C̃u_{K}.

5. Output the vector v composed of its subvectors v_{M} = u_{M} and v_{K}.

The use of Cauchy matrix C is due to the next theorem, which also implies the correctness of Algorithms 3.1 [MS77].

Theorem 3.1 (cf. e.g. [M82]). Every square submatrix of the matrix C = (\frac{1}{s_{i}+t_{j}})_{i,j} is nonsingular if all n values s_{i}, −t_{j} are distinct.

4 Computational cost estimates

No ops are used at Stages 2 and 5 of Algorithm 3.1. The asymptotic computational complexity at stages 1, 3 and 4 can be estimated by using the known algorithms of [Ga60] and

[Ge87] for computations with Cauchy matrices. In particular, due to the structure of a Cauchy matrix C, it can be stored economically (if we represent it by n parameters s_{i}, t_{j}) and multiplied by a vector fast (cf. [Ge87] or [BP94], p.130):

Proposition 4.1 A k × k Cauchy matrix can be multiplied by a vector in O(M(k) log k) ops (for M(k) of (2.1)).

Furthermore, we have (cf. [Ga60] or [BP94], p. 131):

Proposition 4.2 O(M(n) log k) ops suffice to solve a linear system of k equations with a k × k Cauchy coefficient matrix.

The computation of the vectors u at stage 1 and v at stages 3 and 4 of Algorithm 3.1 requires only O(M(ℓ)(log ℓ)n/ℓ) = O((n log^{2} ℓ) log log ℓ) and O(M(k) log k) = O((k log^{2} k) log log k) ops, respectively (cf. (2.1),(2.5)). Practically, the users prefer asymptotically slower algorithms that require (O((n − m)m), O(k^{2}), and O(k^{2}) ops at stages 1, 3 and 4, respectively (cf. [BKKKLZ95]). This is because the algorithms of [Ga60], [Ge87] rely on asymptotically fast polynomial interpolation and multipoint evaluation, which involve (particularly the interpolation) larger overhead constants. Our algorithm supporting the next theorem (where we use relations (2.1)-(2.5)) improves the cited asymptotically fast computations by reducing the overhead constants substantially and by accelerating encoding by logarithmic factor (cf. also Remarks 7.1 and 8.1 in sections 7 and 8).

Theorem 4.1 Algorithm 3.1 can be performed by using O((n/ℓ)M(ℓ)) ops at stage 1 (for ℓ of (2.5)), O(H(k) + E(k)) at stage 3, and O(E(k) + M(k)) at stage 4 provided that the matrix C̃ is represented in factorized form with 4k parameters (rather than with its k^{2} entries), and similarly the input matrix C is represented by the n parameters s_{i}, t_{j}. At all stages, the computation requires only linear memory space.

Our first observation towards the proof of Theorem 4.1 is that in the encoding/decoding process the integers m and n are given by users, the set Q is defined by the uncontrolled erasure process in the transmission of the message, and we may choose any vectors s and t. We will use this choice to impose some additional structure on the Cauchy matrix C.

5 Cauchy matrices with Hankel/Toeplitz structrure

H = (h_{i,j}) (resp. T = (t_{i,j})) is a Hankel (resp. Toeplitz) matrix if h_{i+1,j−1} = h_{i,j} (resp. t_{i+1,j+1} = t_{i,j}) for all i, j for which h_{i+1,j−1} and h_{i,j} (resp. t_{i+1,j+1} and t_{i,j}) are defined.

Fact 5.1 H is a Hankel matrix, and T is a Toeplitz matrix if and only if so are their transposes.

Theorem 5.1 (cf. [BP94] and Lemma 2.2). O(M(l)n/l) ops and O(n) memory space suffice to multiply an (n − m) × m Hankel or Toeplitz matrix by a vector, for ℓ of (2.5).

We immediately observe

Fact 5.2 A Cauchy matrix C = (\frac{1}{s_{i}−t_{j}}) is a Hankel matrix if and only if s_{i+1}−s_{i} = t_{j} −t_{j+1} for all pairs (i, j) for which s_{i+1}, s_{i}, t_{j+1}, and t_{j} are defined. C is a Toeplitz matrix if and only if s_{i+1} − s_{i} = t_{j+1} − t_{j} for all pairs (i, j) for which s_{i+1}, s_{i}, t_{j+1}, and t_{j} are defined.

In particular, C = (\frac{1}{i+j+a})_{i,j} is a Hankel matrix, C = (\frac{1}{i−j+a})_{i,j} is a Toeplitz matrix, for any scalar a such that i + j + a ≠ 0 (or resp. i − j + a ≠ 0) for all pairs (i, j) from the allowed range.

By choosing a Cauchy matrix C of this kind as our input to Algorithm 3.1, we achieve the desired time and space complexity bounds at stage 1.

6 The inverse of a Cauchy matrix

Theorem 6.1 (cf. e.g. [R89] or [BP94], p. 131). Let p = (p_{i})_{i=0}^{k−1}, q = (q_{i})_{i=0}^{k−1}, where p_{0}, q_{0}, …, p_{k−1}, q_{k−1} are distinct. Then det C(p, q) ≠ 0 and C^{−1}(p, q) = D_{0}C(q, p)D_{1}, where D_{0} = diag((−1)^{i} \frac{h_{p}(q_{i})}{h′_{q}(q_{i})})_{i=0}^{k−1}, D_{1} = diag((−1)^{j} \frac{h_{q}(p_{j})}{h′_{p}(p_{j})})_{j=0}^{k−1}.

Theorem 6.2 (cf. e.g. [BP94]). Given two vectors p, q ∈ F^{k}, it suffices to use O(H(k) + E(k)) = O(M(k) log k) (for M(k), H(k) and E(k) of (2.1)-(2.3)) ops to compute the coefficients of the polynomials h_{p}(x), h_{q}(x), h′_{p}(x), and h′_{q}(x) and the vectors ((−1)^{i}h_{p}(q_{i})/h′_{q}(q_{i}))_{i=0}^{k−1} and ((−1)^{j}h_{q}(p_{j})/h′_{p}(p_{j}))_{j=0}^{k−1}, defining the matrices D_{0} and D_{1} of Theorem 6.1.

We also observe the following simple facts:

Fact 6.1 If C(p, q) = (C(s, t))_{K,J}, then C(q, p) = (C(t, s))_{J,K}.

Fact 6.2 C(t, s) = −C^{T} (s, t).

By combining Theorems 5.1, 5.2, 6.1, 6.2, Proposition 4.1, and Facts 5.1, 5.2, 6.1 and 6.2, we obtain the desired complexity bounds at stages 1 and 3 of Algorithm 3.1 (cf. the end of the previous section).

Corollary 6.1 Let vectors s, t satisfy the assumptions of Fact 5.3, that is, let the Cauchy matrix C = C(s, t) be also a Hankel (or Toeplitz) matrix. Then Stage 1 of Algorithm 3.1 involves O(n) memory space and O(H(k) + E(k)) = O(M(ℓ)n/ℓ) ops for M(ℓ) of (2.1) and ℓ = min{m, n − m}, whereas Stage 3 requires O(k) memory space and O(H(k) + E(k)) = O(M(k) log k) ops to compute the diagonal matrices D_{0}, D_{1} of Theorem 6.1, defining the matrix C^{−1}(p, q) in the factorized form D_{0}C(q, p)D_{1}, where p = s_{J}, q = t_{K}. Furthermore, the matrix C(q, p) = (C(s, t))_{K,J} is a submatrix of the (n − m) × m Cauchy and Hankel (or Toeplitz) matrix C(s, t).

7 Computational cost of multiplication of the inverse of a Cauchy matrix by a vector

The k × k diagonal matrices D_{0} and D_{1} are multiplied by a vector in 2k ops. Therefore, the cost of multiplication by a vector of the k × k matrix E = C^{−1}(p, q) = D_{0}C(q, p)D_{1}, for p = s_{J}, q = t_{K}, is dominated by the cost of multiplication of the k × k Cauchy matrix C(q, p) by a vector (Trummer’s problem). We propose to solve this problem based on the following factorization:

Fact 7.1 [FHR93]. C(q, p) = (diag(h_{p}(q_{i}))_{i=0}^{k−1})^{−1}V (q)H(p)V^{T} (p), where H(p) = (h_{i,j}) is a triangular Hankel matrix, h_{i,j} = p_{i+j} where i + j < k, h_{i,j} = 0 where i + j ≥ k, p = (p_{i})_{i=0}^{k−1}.

We observe that the values h_{p}(q_{i}), i = 0, …, k − 1, are available from stage 3 (actually, the factor (diag(h_{p}(q_{i}))_{i})^{−1} of Fact 7.1 and the numerator-diagonal of D_{0} cancel each other). By combining Lemmas 2.3 and 2.4 with Theorem 5.1, we obtain the solution of Trummer’s problem of multipication of C(q, p) by a vector by using O(E(k) + M(k)) = O(M(k) log k) ops. This completes the proof of Theorem 4.1. □

Remark 7.1 An alternative way to fast decoding is to embed the matrix C(q, p) into C(t, s) and then to apply Theorem 5.1 and Lemma 2.1. Such a solution of Trummer’s problem for C(q, p) involves O(M(l)n/l) ops (as at the encoding stage), which may improve the estimate O(H(k) + E(k)) of Theorem 4.1, depending on how large k is versus n. The same observations apply to the algorithms of the next two sections.

8 An alternative choice of a Cauchy matrix

If the field F supports FFT on the set of the r-th roots of 1 for r ≥ max{m, n − m}, we may improve encoding by assigning, say, s_{i} = aω_{r}^{i}, i = 0, …, n − m − 1; t_{j} = bω_{r}^{n−m+j}, j = 0, …, m − 1, where ω_{r} is a primitive r-th root of 1, and the scalars a and b are chosen to insure that the n values as_{i} and bt_{j} are all distinct. In this case, we factorize the Cauchy matrix C(s, t) based on Fact 7.1, compute or pre-compute the coefficients of the polynomial h_{t}(x) = ∏_{j=0}^{m−1}(x−aω_{r}^{n−m+j}) (at the cost at most H(m)), then its values h_{t}(s_{i}), i = 0, …, n − m − 1 (by applying FFT), and finally multiply C(s, t) by a vector v based on Lemma 2.5, Remark 2.1 and Theorem 5.1.

Remark 8.1 If we embed the matrices V (q) and/or V^{T} (p) into V (t) and/or V^{T} (s), respectively, and then apply Lemma 2.5 and Remark 2.1, then the multiplication of V (q) and/or V^{T} (p) by a vector will involve O(M(m)) and/or O(M(n − m)) ops, respectively, which may improve the bound O(M(k) log k), depending on how large k is versus m and/or n − m.

9 A variant of encoding

Assuming that the field F contains the r-th roots of 1, for r ≥ max{m, n − m}, we may try to simplify further the encoding stage, by reducing it essentially to two discrete Fourier transforms on the set of the r-th roots of 1.

We will start with some definitions. We write w = (ω_{r}^{i})_{i=0}^{r−1}, where ω_{r} is a primitive r-th root of 1; Ω = (ω^{ij})_{i,j=0}^{r−1}, Ω denoting the matrix of DFT.

For a scalar e, we define the r × r unit e-circulant matrix, T_{e} = (t_{i,j})_{i,j=0}^{r−1}, t_{i,j} = 1 for i = j + 1, t_{i,j} = e for i = 0, j = r − 1, t_{i,j} = 0 for other i, j. The matrix T_{e} generates the class of e-circulant matrices, T_{e}(v) = ∑_{i=0}^{r−1} v_{i}T_{e}^{i}, for all vectors v = (v_{i})_{i=0}^{r−1}. (This is a subclass of the class of Toeplitz matrices.) We write D(v) = diag(v_{i})_{i=0}^{r−1}.

Theorem 9.1 Let g, h, e = g^{r}, f = h^{r} be four nonzero scalars, e ≠ f, let e = (g^{i})_{i=0}^{r−1}, f = (h^{i})_{i=0}^{r−1}, U_{e} = ΩD(e), U_{f} = ΩD(f), and let the vector U_{f}(v) (for a given vector v) have no zero components. Furthermore, let the vectors gw and hw have 2r distinct components, that is, let the Cauchy matrix Ĉ = C(gw, hw) be well defined and nonsigular. Then Ĉ = \frac{1}{e−f} D^{−1}(U_{f}(v))U_{f}T_{e}(v)U_{e}^{−1}D^{−1}(U_{e}^{−1})^{T} e^{(r−1)}).

Proof. Theorem 9.1 is deduced from Proposition 6.3 of [P99]. □ Now, let r ≥ max{m, n − m}, fix two nonzero scalars, g and h, and a vector v (say, v =

e^{(1)}) satisfying the assumptions of Theorem 9.1, and define the matrix C(s, t) ∈ F^{(n−m)×m} being a block of the matrix Ĉ of (9.1). In this case, Trummer’s problem of multiplication of Ĉ (and hence also of C(s, t)) by a vector is reduced essentially (up to performing O(n) ops) to multiplication of the matrices Ω and (Ω^{−1})^{T} by a vector, that is, to two discrete Fourier transforms on the set of the r-th roots of 1, because the choice of v = e^{(i)} for any i from 1 to r − 1 trivializes the computation of the vector U_{f}v and the multiplication of T_{e}(v) by a vector. Actually, the computations are further simplified because we only multiply the submatrix C(s, t) of Ĉ (rather than Ĉ itself) by a vector. Further minor simplification is yielded for e = 1 or f = 1 because D(1) = I_{r} and, therefore, U_{1} = Ω.

10 Discussion

Various further modifications of the proposed approach are possible and may lead to some further improvements. For instance, one may try to improve the decoding stage based on the following expressions:

C^{−1}(p, q) = (diag(h′_{q}(q_{i}))_{i=0}^{k−1})^{−1} V (q)V^{−1}(p)diag(h_{q}(p_{i}))_{i=0}^{k−1},

V^{−1}(p) = RT_{f}(h_{p} + fe^{(0)})V^{T} (p)(diag(h′_{p}(p_{i})(f − p_{i}^{n}))_{i=0}^{k−1})^{−1},

where f is a scalar, p_{i}^{n} ≠ f for i = 0, …, k − 1, h_{p} = (h_{i})_{i=0}^{k−1} for h_{0}, …, h_{k−1} satisfying the equation x^{k} +∑_{i=0}^{k} h_{i}x^{i} = ∏_{i=0}^{k−1}(x−p_{i}), e^{(0)} = (1, 0, …, 0)^{T}, and R is the reversion matrix, R = (r_{i,j}), r_{i,j} = 1 for i = k − 1 − j, r_{i,j} = 0 otherwise (cf. [FHR93], [BP94], p.144). In this case, one may multiply V^{T} (p) by a vector based on Tellegen’s theorem (cf. Lemmas 2.3 and 2.4).

References

[ABELS94] A. Albanese, J. Blömer, J. Edmonds, M. Luby, M. Sudan, Priority Encoding Transmission, Proc. 35th Ann. Symp. Foundations of Computer Science (FOCS), 604-613, IEEE Computer Society Press, 1994.

[AEL95] N. Alon, J. Edmonds, M. Luby, Linear Time Erasure Codes with Nearly Optimal Recovery, Proc. 36th Ann. Symp. Foundations of Computer Science (FOCS), IEEE Computer Society Press, 1995.

[BP94] D. Bini, V.Y. Pan, Polynomial and Matrix Computations, Volume 1: Fundamental Algorithms, Birkhäuser, Boston, 1994.

[BKKKLZ95] J. Blömer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, D. Zuckerman, An XOR-Based Erasure-Resilient Coding Scheme Technical Report TR-95-48, International Computer Science Institute, Berkeley, Califormia, 1995.

[FHR93] T. Fink, G. Heinig, K. Rost, An Inversion Formula and Fast Algorithms for Cauchy-Vandermonde Matrices, Linear Algebra Appl., 183, 179–191, 1993.

[Ga60] N. Gastinel, Inversion d’une Matrice Generalisant la Matrice de Hilbert, Chiffres, 3, 149-152, 1960.

[Ge87] A. Gerasoulis, A Fast Algorithm for the Multiplication of Generalized Hilbert Matrices with Vectors, Math. Comp., 50, 181, 179-188, 1987.

[Go85] G. H. Golub, Trummer’s Problem, SIGACT News, 17, 2, 12, ACM Press, New York, 1985.

[M82] L. Mirsky, An Introduction to Linear Algebra, Dover, New York, 1982.

[MS77] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, New York, 1977.

[P90] V. Y. Pan, Computations with Dense Structured Matrices, Math. of Computation, 55, 191, 179–190, 1990.

[P99] V. Y. Pan, Nearly Optimal Computations with Structured Matrices, preprint, 1999.

[PACLS98] V. Y. Pan, M. AbuTabanjeh, Z. Chen, E. Landowne, A. Sadikou, New Transformations of Cauchy Matrices and Trummer’s Problem, Computer and Math. (with Applics.), 35, 12, 1-5, 1998.

[PSD70] P. Penfield Jr., R. Spencer, S. Duinker, Tellegen’s Theorem and Electrical Networks, MIT Press, Cambridge, Massachusetts, 1970.

[R89] M. O. Rabin, Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance, J. ACM, 36, 2, 335-348, 1989.

[WB94] S. B. Wicker, V. Bhargava, Reed-Solomon Codes and Their Applications, IEEE Press, New York, 1994.