ABSTRACT

The task of determining the greatest common divisors (GCD) for several polynomials which arises in image compression, computer algebra and speech encoding can be formulated as a low rank approximation problem with Sylvester matrix. This paper demonstrates a method based on structured total least norm (STLN) algorithm for matrices with Sylvester structure. We demonstrate the algorithm to compute an approximate GCD. Both the theoretical analysis and the computational results show that the method is feasible.

1. Introduction

Let be the degree of and be the set of univariate polynomials. stands for the spectral norm of the matrix. and are the vector spaces of complex vectors and matrices, respectively. Transpose matrices and vectors are denoted by and. denotes the greatest common divisor for the polynomials and. We use to stand for the rank of matrix.

In this paper, we consider the following problem. Let , namely

Problem 1.1. Set be a positive integer with. We wish to compute such that

and

is minimized.

The problem of computing approximate GCD of several polynomials is widely applied in speech encoding and filter design [1], computer algebra [2] and signal processing [3] and has been studied in [4-7] in recent years. Several methods to the problem have been presented. The generally-used computational method is based on the truncated singular decomposition (TSVD) [8] which may not be appropriate when a matrix has a special structure since they do not preserve the special structure (for example, Sylvester matrix). Another common method based on QR decomposition [9,10] may suffer from loss of accuracy when it is applied to ill-conditioned problems and the algorithm derived in [11] can produce a more accurate result for ill-conditioned problems. Cadzow algorithm [12] is also a popular method to solve this problem which has been rediscovered in the literature [13].

Somehow it only finds a structured low rank matrix that is nearby a given target matrix but certainly is not the closet even in the local sense. Another method is based on alternating projection algorithm [14]. Although the algorithm can be applied to any low rank and any linear structure, the speed may be very slow. Some other methods have been proposed such as the ERES method [15], STLS method [16] and the matrix pencil method [17]. An approach to be described is called Structured Total Least Norm (STLN) which has been described for Hankel structure low rank approximation [18,19] and Sylvester structure low rank approximation with two polynomials [20]. STLN is a problem formulation for obtaining an approximate solution to an overdetermined linear system preserving the given structure in or.

In this paper, we apply the algorithm to compute the structured preserving rank reduction of Sylvester matrix. We introduce some notations and discuss the relationship between the GCD problems and low rank approximation of Sylvester matrices in Section 2. Based on STLN method, we describe the algorithm to solve Problem 1.1 in Section 3. In Section 4, we use some examples to illustrate the method is feasible.

2. Main Results

First of all, we shall prove that Problem 1.1 always has a solution.

Theorem 2.1. Suppose that , and are defined as those in Problem 1.1. There exist, with, and

such that for all, with, and

.

We have

Proof. Let be monic with and set with. For the real and imaginary parts of the coefficients of and of . We are considered with the continuous objective function

We will prove that the function has a value on a closed and bounded set of its real argument vector which is smaller than elsewhere. Consider and with a GCD of degree for. Clearly, any and with

can be discarded. So from above,we know that the coefficients of can be bounded and so can the coefficients of by any polynomials factor coefficient bound. Thus the function’s domain is restricted to a sufficiently large ball. It remains to exclude as the minimal solution. We have

.

In conclusion, the theorem is true.

Now we begin to solve Problem 1.1, we first define a matrix associated with as follows

and an matrix associated with as

An extended Sylvester matrix or a generalized resultant is then defined by

Deleting the last rows of and the last columns of coefficients of  separately is, We get the -th Sylvester matrix

It is well-known that if and only if has rank deficiency at least 1. We have

(2.1)

where is the -th Sylvester matrix generated by .

From above, we know that (2.1) can be transformed to the low rank approximation of a Sylvester matrix.

If we use STLN [16] to solve the following overdetermined system

for, where is the first column of and are the remainder columns of, then we get a minimal perturbation of Sylvester structure satisfying

So the solution with Sylvester structure is and.

We will give the following example and theorem to explain why we choose the first column to form the overdetermined system.

Example 2.1. Suppose three polynomials are given

The matrix is the Sylvester matrix generated by

and

The matrix is partitioned as or, where is the first column of, whereas is the last column of.

The overdetermined system

has a solution, while the system

has no solution.

Theorem 2.2. Suppose that , and are defined as those in Problem 1.1 and is the -th Sylvester matrix of . Then the following statements are equivalent.

1);

2) has a solution, where is the first column of and are the remainder columns of.

Proof. Suppose has a nonzero solution, then. Since is the first column of, obviously, the dimension of the rank deficiency of is at least 1.

Suppose the rank deficiency of is at least 1 and, . Multiplying the vector to the matrix, then we obtain

(2.2)

Next we will prove that has a solution. If we multiply the vector to two sides of the equation, it turns out to be

(2.3)

The solution of equation (2.3) is equal to the coefficients of polynomials such that

We can get and from . Dividing by, we obtain a quotient and a remainder satisfy

where . Now we can get that

are solutions of Equation (2.3), since

and

Next, we will illustrate for any given Sylvester matrixas long as all the elements are allowed to be perturbed, we can always find -Sylvester structure matrices satisfy, where is the first column of and are the remainder column of.

Theorem 2.3. Given the positive integer, there exists a Sylvester matrix with rank deficiency k.

Proof. We can always find polynomials with, and. Hence is the Sylvester matrix of and its rank deficiency is k.

Corollary 2.1. Given the positive integer, and -th Sylvester matrix, where , , it is always possible to find a -th Sylvester structure perturbation such that.

3. STLN for Overdetermined System with Sylvester Structure

In this section, we will use STLN method to solve the overdetermined system

According to theorem 2.3 and corollary 2.1, we can always find Sylvester structure with . Next we will use STLN method to find the minimum solution.

First, we define the Sylvester structure preserving perturbation of

can be represented by a vector

.

We can define a matrix such that.

where is a identity matrix.

We will solve the equality-constrained least squares problem

(3.1)

where the structured residual is

By using the penalty method, the formulation (3.1) can be transformed into

(3.2)

where is a large penalty value.

Let and stand for a small change in and, respectively and be the corresponding change in. Then the first order approximate to is

Introducing a matrix of Sylvester structure and

(3.2) can be approximated by

(3.3)

where satisfies that

(3.4)

In the following, we present a method to obtain the matrix. Suppose and are defined as above. Multiplying the vector

to the two sides of equation (3.4), it becomes

Let, we obtain

(3.5)

where is the polynomial with degree which is generated by the subvector of:

is the polynomial with degree which is generated by the subvector of:

is the polynomial with degree which is generated by the subvector of:

is the polynomial with degree which is generated by the subvector of:

is the polynomial with degree which is generated by the subvector of:

is the polynomial with degree which is generated by the subvector of:

Here we will present a simple example to illustrate how to find.

Example 3.1. Suppose, and

then

4. Approximate GCD Algorithm and Experiments

The following algorithm is designed to solve Problem 1.1.

Algorithm 4.1.

Input-A Sylvester matrix S generated by , respectively, an integer and a tolerance.

Output-Polynomials and the Euclidean distance is to a minimum.

1) Form the -th Sylvester matrix as the above section, set the first column of as and the remainder columns of as. Let.

2) Calculate from and. Compute and as the above section.

3) Repeat

(1)

(2) Let

(3) Form the matrix and from, and from. Let

until and

4) Output the polynomials constructed from

Given a tolerance, we can use the Algorithm 4.1 to compute an approximate GCD of. The method begin with using Algorithm 4.1 to compute the minimum perturbation

with. If, then we can compute the approximate GCD form matrix. Otherwise, we reduce by one and repeat the Algorithm 4.1.

Example 4.1. We wish to find the minimal polynomial perturbations and of

satisfy that the polynomials and have a common root. We take two cases into account.

Case 1: The leading coefficients can be perturbed. Let and, after 3 iterations, we get the polynomials and

with a minimum distance

Case 2: The leading coefficients can be perturbed. Let and, after 3 iterations, we have the polynomials and:

with a minimum distance

Example 4.2. Let, and

after 8 iterations, we have the polynomials

with a minimum distance

and the CPU time

Example 4.3. Let, and

after 11 iterations, we have the polynomials

with a minimum distance

and the CPU time

Example 4.4. Let, and

after 1 iteration, we have the polynomials

with a minimum distance

and the CPU time

Example 4.5. Let, and

after 1 iteration, we have the polynomials

with a minimum distance

and the CPU time

Examples 4.1, 4.2, 4.3, 4.4 and 4.5 show that Algorithm 4.1 is feasible to solve Problem 1.1.

In Table 1, we present the performance of Algorithm 4.1 and compare the accuracy of the new fast algorithm with the algorithms in [9,21]. Denote be the total degree of polynomials and be the total degree of polynomials. It (Chu) stands for the number of iterations by the method in [14] whereas it (STLN) denotes the number of iterations by Algorithm 4.1. Denoted by error(Zeng) and error (STLN) are the perturbations computed by the method in

[21] and Algorithm 4.1, respectively. The last two columns denote the CPU time in seconds costed by AFMP algorithm and our algorithm, respectively.

As shown in the above table, we show that our method based on STLN algorithm converges quickly to the minimal approximate solutions, needing no more than 2 iterations whereas the method in [14] requires more iteration steps. We also note that our algorithm still converges very quickly when the degrees of polynomials become large while the algorithm in [14] needs more iteration steps. Besides, our algorithm needs less CPU time than the AFMP algorithm. So the convergence speed of our method is faster. From the errors, we demonstrate that our method has smaller magnitudes compared with the method in [21]. So our algorithm can generate much more accurate solutions.

5. Conclusion

In this paper, we present that approximation GCD of several polynomials can be solved by a practical and reliable way based on STLN method and transformed to the approximation of Sylvester structure problem. For the matrices related to the minimization problems are all structured matrix with low displacement rank, applying the algorithm to solve these minimization problems would be possible. The complexity of the algorithm is reduced with respect to the degrees of the given polynomials. Although the problem of structured low rank ap-

proximation has been studied in many literatures and obtained many accomplishments, there is still much work to be done, for example, low rank approximation of finite dimensional matrix has not been fully resolved.

REFERENCES

NOTES

^*The author is supported by a grant from National Natural Science Foundation of China (11101100; 11391240185; 11261014; 11226323) and Natural Science Foundation of Guangxi Province (No.2012GXN SFBA053006; 2013GX NSFBA019009; 2011GXNSFA018138).