Laure Berti-Équille
email: laure.berti-equille@irisa.fr

QUALITY-ADAPTIVE QUERY PROCESSING OVER DISTRIBUTED SOURCES (Research-in-Progress)

Keywords: Data Quality, Source Quality, QML, Quality of Service, Negotiation, Adaptive Query Processing

For non-collaborative data sources, both cost estimate-based optimization and quality-driven query processing are difficult to achieve because the sources do not export cost information nor data quality indicators. In this paper, we first propose an expressive query language extension using QML 1 syntax for defining in a flexible way dimensions, metrics of data quality and data source quality. We present a new framework for adaptive query processing on quality-extended query declarations. This processing includes the negotiation of quality contracts between the distributed data sources. The principle is to find dynamically the best trade-off between the cost of the query and the quality of the result retrieved from several distributed sources.

INTRODUCTION

For the mediator/wrapper architecture, the access to distributed information sources is carried out in a declarative way. The mediator processes the queries of the users at the global level and optimizes the query plans according to the wrappers that reach respectively their underlying data sources. In this type of environment, the sources are usually non-collaborative and do not export information describing the local costs of query processing, neither indicators of their quality of service (e.g., resource accessibility, reliability, security, etc.) nor information describing the quality of their content (e.g., data accuracy, freshness, completeness, etc.). Not provided, this information has to be estimated, computed dynamically and updated if provided. But, the lack of scalability and flexibility face to the growing number and the changing structure of data sources harm seriously the effectiveness of dynamic execution of distributed queries and the quality of results. Although there are several approaches that deal with the assessment and the management of quality metadata, the dual problem of fixing the query cost and optimizing the result quality, or fixing the result quality and optimizing the query cost still remains. Querying simultaneously several data sources in a dynamic and distributed environment raises several interesting problems and open issues as follows:

-Selecting dynamically appropriate sources: different information sources may answer the global query with different response times, query costs and various levels of result quality. How to define strategies for selecting adaptively the most appropriate sources for answering the whole or parts of the global query with the right quality? Which are the criteria to select the best quality sources on the fly?

-Defining semantically and qualitatively correct distributed query plans: the result of a global 1 Quality of Service Modeling Language proposed by Frølund and Koistinen [START_REF] Frølund | QML: A Language for Quality of Service Specification[END_REF] Proceedings of the Ninth International Conference on Information Quality (ICIQ-04)

query is built according to the particular order for execution of subquery plans. This must combine in a coherent way both information and meta-information from the various sources; but data quality levels are often unknown, heterogeneous from one source to another (inter-source quality heterogeneity) and locally non uniform (intra-source quality non-uniformity): in this context, the aim is to control and merge data quality indicators in a consistent way for both correctly integrating data and quality metadata -Making trade-offs between the query cost and the final and perceived result quality (including both the quality of service and the quality of content): because we may accept a query result of lower quality (if it is cheaper or has a shorter response time than if the query cost is higher), it's necessary to adapt query costs to users' quality requirements. The objective is to measure and optimally reduce the cost and bargain query situations where the system searches for solutions that "squeeze out" more gains (in terms of result quality) than the query without quality requisites.

-Developing concrete cost models to evaluate whether the expected benefits from the improved query plan and decision quality compensate for the cost of collecting and evaluating feedback from the environment during execution time. The difficulty is to adapt existing query processing techniques to environments where resource availability, allocation, quality and cost are not, by definition, decidable at compile time.

For these open questions, some solutions have been proposed in the literature, but very few approaches use the quality of service approach together with the quality of data techniques for adapting query processing. In this context, our objectives are: (i) to extend a generic query language for describing and manipulating, in a flexible way, data and source quality contracts, (ii) to propose a new query processing framework for selecting dynamically sources with quality-extended queries with a negotiation strategy.

This paper describes XQuaL -QML-extended Query Language -and the negotiation processing over distributed sources with heterogeneous quality. While our general approach to query processing is typical, a number of factors associated with quality constraints specification and negotiation complicate the problem of distributed query processing. The challenges have been to choose an appropriate formalism for specifying, in a flexible way, quality metadata (dimensions and metrics) and to devise methods for quality-extended query processing including a quality-based negotiation algorithm.

The paper is organized as follows. In Section 2, we briefly present previous work in the areas of quality of service (QoS) and of quality of Data (QoD). In Section 3, we describe the specifications of our query language extension. In Section 4, we present the definitions and the algorithm for the negotiation for the quality-extended query processing. In Section 5, we present an illustrative example. Section 6 concludes the paper and presents our future work. definition raising new problems. Traditional quality of service categories and dimensions (such as execution time or cost) are now extended to integrate the concepts of data quality and source quality as well as quality of provided services (such as searching techniques, optimization strategies, data transfer, adaptation or presentation). In this context, the QML language (Quality of service Modeling Language) has been proposed by Frølund and Koistinen [START_REF] Frølund | QML: A Language for Quality of Service Specification[END_REF] in order to deal with the quality of service of software components in a systematic and declarative manner, allowing flexible definition of quality dimensions, quality contracts and profile constraints. We found relevant to adapt the language QML for extending SQL-like query language syntax and querying data with quality requirements.

RELATED WORK: WHEN QOS MEETS QOD

Quality of Data

Literature on data quality proposes definitions, metrics, conceptual models and methodologies to improve data quality in databases (see Dasu and Johnson [6,[START_REF] Dasu | Mining database structure or, how to build a data quality browser[END_REF]), information systems (see Wang [START_REF] Wang | Journey to Data Quality[END_REF][START_REF] Wang | A product perspective on Total Data Quality Management[END_REF][START_REF] Strong | Data quality in context[END_REF], Ballou and Pazer [START_REF] Ballou | Modeling completeness versus consistency tradeoffs in information decision contexts[END_REF], Pipino and Lee [START_REF] Pipino | Data quality assessment[END_REF], Fox, Letivin and Redman [START_REF] Fox | The notion of data and its quality dimensions[END_REF], [START_REF] Redman | Data quality for the information age[END_REF]) and data warehouse systems (e.g., DWQ -Data Warehouse Quality, see Clavanese et al., [START_REF] Clavanese | Data integration in Datawarehousing[END_REF], Vassiliadis [START_REF] Vassiliadis | Data Warehouse Modeling and Quality Issues[END_REF][START_REF] Vassiliadis | ARKTOS: A Tool For Data Cleaning and Transformation in Data Warehouse Environments[END_REF]). Most of the approaches are centered on various methods of imputation such as inferring missing data from statistical patterns of available data sets, predicting accuracy of the estimates based on the given data, data edits (automatic detection and handling of outliers in data), error control (see Paradice and Fuerst [START_REF] Paradice | An MIS data quality management strategy based on an optimal methodology[END_REF]). Various methods were developed to measure the data quality provided to the users in conformance to their quality specifications or by comparison with a referential database. The use of metadata for evaluation and improvement of data quality was also recommended by Rothenberg [START_REF] Rothenberg | Metadata to support data quality and longevity[END_REF] where information producers were encouraged to carry out the verification, the validation, and the certification (VV&C) of their data.

The most frequently mentioned data quality dimensions in the literature are accuracy, completeness, freshness and consistency:

-Correctness is measured by detecting the rate of incorrect values in the database (see Hou, Zhang, [START_REF] Hou | Enhancing database correctness: a statistical approach[END_REF]), -Completeness is measured by detecting the rate of missing values in the database, -Freshness is measured by detecting the rate of obsolete values in the database, -Consistency is measured by comparison with a set of constraints by detecting the data, which do not satisfy them. But many others dimensions, metrics and measurement techniques have been proposed in the literature (by Fox, Letivin, Redman, [START_REF] Fox | The notion of data and its quality dimensions[END_REF][27], Naumann [START_REF] Naumann | Quality-Driven Query Answering for Integrated Information Systems[END_REF][START_REF] Naumann | Quality-driven integration of heterogeneous information systems[END_REF], by Kahn, Strong, Wang [START_REF] Kahn | Information quality benchmarks: product and service performance[END_REF], by Ballou and Pazer [START_REF] Ballou | Modeling completeness versus consistency tradeoffs in information decision contexts[END_REF]). The general trend is the use of Artificial Intelligence methods (training, knowledge representation schemes, management of uncertainty, etc.) for purposes of data validation (see Maletic, Marcus [START_REF] Maletic | Data Cleansing: Beyond Integrity Analysis[END_REF], Lee et al. [START_REF] Lee | Cleansing Data for Mining and Warehousing[END_REF], Fayyad, Piatetshy-Shapiro [START_REF]Advances in Knowledge Discovery and Data Mining[END_REF], Winkler [START_REF] Winkler | Data Cleaning Methods, Intl. Conf. KDD[END_REF], Dasu and Johnson [START_REF] Dasu | Exploratory Data Mining and Data cleaning[END_REF][START_REF] Dasu | Mining database structure or, how to build a data quality browser[END_REF]. The use of machine learning techniques for data validation and correction was first presented by Parsaye, Chignell [START_REF] Parsaye | Intelligent Database Tools and Applications[END_REF]: rules inferred from the database instances by machine learning methods were used to identify outliers in data and facilitate data validation process. Another similar approach was proposed by Schlimmer [START_REF] Schlimmer | Learning determinations and checking databases[END_REF][START_REF] Schlimmer | Self-modeling databases[END_REF]. Utilization of statistical techniques for improving the correctness of the databases and introduction of a new kind of statistical integrity constraints were also proposed by Hou and Zhang [START_REF] Hou | Enhancing database correctness: a statistical approach[END_REF]. Statistical constraints are derived from the database instances using conventional statistical techniques (sampling, regression).

Other propositions concern the definition of declarative language extensions for specifying/querying quality metadata (Q-Data by Sheth, Wood, Kashyap [START_REF] Sheth | Q-data: Using deductive database technology to improve data quality[END_REF]) or for applying data transformations necessary to specific cleaning process (AJAX by Galhardas et al. [START_REF] Galhardas | An Extensible Framework for Data Cleaning[END_REF], ARKTOS [START_REF] Vassiliadis | ARKTOS: A Tool For Data Cleaning and Transformation in Data Warehouse Environments[END_REF], Potter's Wheel [START_REF] Raman | Potter's wheel: an interactive data cleaning system[END_REF]). The prototype described of Sheth, Wood, Kashyap [START_REF] Sheth | Q-data: Using deductive database technology to improve data quality[END_REF] checks if the existing data are correct: the authors call it data validation and cleanup by using a logical database language (LDL++). The system employs data validation constraints and data cleanup rules. AJAX [START_REF] Galhardas | An Extensible Framework for Data Cleaning[END_REF] is an SQL extension for specifying each data transformation (such as matching, merging, mapping, clustering) for the data cleaning process. These transformations standardize data formats when possible and find pairs of records that most probably refer to the same object. The duplicate-elimination step is applied if approximate duplicate records are found and multi-table matching computes a similarity join between distinct data flows and consolidates them.

Among the projects that have been proposed for data quality in distributed environments: HiQ B&B (High Quality Branch and Bound Algorithm) proposed by Naumann [START_REF] Naumann | Quality-Driven Query Answering for Integrated Information Systems[END_REF][22] is a distributed queryplanning algorithm that enumerates plans in such way that it usually finds the best N plans after computing only a fraction of the total number of plans. Upper quality bounds for partial query plans are constructed and thereby non-promising subplans are early pruned in the search tree. This integrates the source and plan quality-based selection phases to a planning algorithm that finds the top N plans for a query distributed over several quality-heterogeneous sources.

Motivations

Positioned between quality of data and quality of service, our approach extends a declarative query language for taking into account, in a flexible way, aspects and constraints related to data source quality. We also adapt the query processing in order to find the trade-off between the query cost and the quality of result. Our query processing framework takes as input a quality-extended query and attempts to adapt the processing to:

1. User preferences and quality requirements. Adapting to user preferences includes cases where users are interested in obtaining some partial results of the query quickly with specific constraints on data quality and source quality of service. In order to meet such needs, the query processor may, for instance, produce results incrementally, as they become available. The user can also classify the elements of the output in terms of importance or quality requisites and, in that case, the query evaluator has to adapt its behavior in order to produce more or better quality results earlier. Thus, the query processor has to consider potential input from the user, such as priority ratings and quality declarations for different parts of the result.

Data source statistics.

In some cases, it is not possible at compile time to gather accurate statistics about the data sources content and quality. A solution to this problem is to collect such statistical information at runtime, thereby ensuring that they are valid for the current circumstances, and to adapt query execution based on it. Techniques that adopt this policy may change the query plan when the actual statistics have become available.

EXTENDING QUERY LANGUAGE WITH QML

The syntax of our quality-extended query language, XQuaL is presented in Appendices and is adapted from Frølund, Koistinen [START_REF] Frølund | QML: A Language for Quality of Service Specification[END_REF] to which we refer the reader for more information. As we will present in the next sections, this language extension is a Data Manipulation Language (DML) with the SQL-like declaration part and also a Data Description Language (DDL) with the contract type declaration defined into the Qwith part.

Quality Metadata Description

A contract is a set of constraints that are defined on different user-specified dimensions. Each contract is an instance of a complex contract type. Figure (1a) proposes examples of contract types declarations for the dimensions called Reliability, Freshness, Completeness, and Credibility and defined as contract types.

Figure (1a). Example of contract types Figure (1b). Example of contract instances

A quality-extended query (Qwith-query) is a SQL-like query followed by a Qwith operator used to declare the types of contracts (contractTypeDeclaration), the contracts (contractDeclaration) or the quality profiles (profileDeclaration) -see Appendices -. Quality can be defined in a flexible way as a specific combination of contract types with a relation of order on data and source quality constraints. Figure 2 presents an example for the definition of quality as a complex contract type using the previously defined contract types of Figure (1a).

type Quality contract { sourceQuality : increasing set {Reliability,Freshness,Completeness,Credibility } with order {Reliability<Completeness, Completeness< Freshness, Freshness < Credibility } } ;

Figure 2. Example of quality contract declaration

Quality Metadata Manipulation

A profile is the set of the required contracts that are affected to one (or several) data source(s) or functionalities. The profiles are useful to associate contracts to sources interfaces (or wrappers). More precisely, a profile declaration (profileDeclaration) is defined with the identifier of the profile, the identifier of the interface and a series of expressions (profileExpression) requiring the satisfaction of contracts by the entities of the targeted interfaces/wrappers (requisites) -see Appendices-.

The profile declaration makes it possible to associate quality contracts with targeted source interfaces and their specific services or methods (such as query_answer_method for source S1 in Figure 3). The clause require binds all the interface/wrapper entities to a list of contracts, whereas the clause from... require... specifically identifies a list of interface entities to which the list of contracts definitions will be associated in the following clause require.

Our contribution is to include the principle of quality contract negotiation over distributed sources and to adapt the query processing. Our objectives are to incorporate a set of primitives and data quality functions that extend the query and that can be computed at runtime and be used for adapting the query processing. Our approach includes: (i) specification of quality requirements or capabilities in the declarative language XQuaL, (ii) negotiation: reaching an agreed specification between all parties (e.g., between the mediator and the wrappers or between the integration system and the sources), (iii) admission control: comparison between the required quality and the capability to meet them, (iv) monitoring: measuring the quality actually provided by the distributed sources, (v) policing: ensuring that all parties adhere to quality contracts, (vi) maintenance: modification of the system parameters to maintain the quality, and (vii) renegotiation: modification of the quality contracts and requisites.

NEGOTIATION FOR QUALITY-EXTENDED QUERY PROCESSING

Definitions

Negotiation can range over number of quantitative and qualitative dimensions of quality. Each successful negotiation requires a range of such dimensions to be resolved to the satisfaction of both parties (i.e. the querying and the queried systems). Making trade-offs between query costs and result quality is required in order to come to an agreement for "good quality" query results. The structure of negotiation is based almost directly on the quality contract used to regulate agreements, which is fairly rich and may cover content quality, service quality and meta-service attributes. Let us now outline the formal basics of our quality-extended query negotiation model.

Let i (i ∈ [1..n]) representing the data sources and j (j ∈ [1..k]) be the dimensions of quality contracts under negotiation (e.g., dataAge, failureMasking, serverFailure, availability numberOfNullValuesPerQuery, etc.). Let x ij ∈ [min ij , max ij ] be a value for the quality dimension j that is acceptable to the user for querying the source i.

At the given time t, each source has a scoring function score ij (t): [min ij , max ij ] → [0,1] that gives the score of the source i assigned to a value of the dimension j in the range of its acceptable values. For convenience, scores are kept in the interval [0,1]. The relative importance that the user assigns to each dimension under negotiation is modeled as a weight, noted w ij , that gives the importance of the dimension j for the source i. We assume the weights are normalized:

∑ ≤ ≤ = k j ij w 1 1 ∀i ∈ [1..n], ∀j ∈ [1..k] (1)
An aggregate scoring function of the source j in the multidimensional space of quality dimensions defined by x = (x 1 ,…,x k ) is defined as :

) , ( . 1 ∑ ≤ ≤ = k j j ij ij i t x score w (x,t) Score (2)
For analytical purposes, we restrict our study to an additive and monotonically increasing or decreasing value scoring function.

Negotiation consists in finding trade-offs between quality profile requisites and effective quality contracts instances of sources during the query processing. The negotiator module decides to make a trade-off action when it does not wish to decrease the aspirational quality level (denoted θ) for a given quality-extended query. The aspirational quality level means the initially required quality. Thus, the negotiator module first computes the quality differential between the effective quality of the sources and the required quality represented by the curve of aspirational quality level θ. And it generates also the contract that lies on the iso-value curve for θ. In practice, the query cost of a query q at a given time t is never null, Cost i (q,t) ∈ ]0,1].

The aim of the trade-off mechanism is to find the contract that is the closest to the initial aspirational curve or the most preferable (i.e, that maximizes the quality and minimizes the query cost). More formally, the aspirational iso-curve and the trade-off are defined as follows:

Definition 1. Aspirational Quality Iso-Curve: Given the required aspirational quality level, noted θ, the iso-curve set at level θ is defined as the set of values of quality dimensions that are the most similar to θ:

(3) iso(θ) = {x j | max(Sim(score ij (x j ),θ j )) ∀i∀j}
The heuristic we employ is to select the contract that is the most "similar" to the negotiator's last proposal (since this may be more acceptable to the user in terms of quality requirements). The similarity between x and y over the set of quality dimensions D is defined as:

y x ce stan di w Sim(x, y) D j j j j j ∑ ∈ = ) , ( . with ∑ ∈ = D j j w 1 (4)
We choose distance j as an Euclidean distance function for dimension j.

Definition 2. Local Trade-Off:

Given a query q and its quality extension x, the local trade-off of the source i, at the given time t, for the quality-extended query (q, x) is defined as follows:

(

Negotiation Strategy

Intuitively, the principle of our negotiation strategy is as follows: we define a system state as the query execution cost and the quality of the source at a given time. Then, we search for the wellbalanced state (i.e., the trade-off) that is the state with the lowest cost and the best quality in conformance with the quality requirements defined into the contracts. Our objective is to find the trade-off state out off in a local minimum state with an adaptation of the simulated annealing process [START_REF] Kirkpatrick | Optimization by Simulated Annealing[END_REF]. First, we choose randomly a candidate source among the sources. We evaluate its cost and quality. We examine others query plans over the sources answering the query and put them into the candidate list even if their costs is greater than the best current one. We accept cost increasing when quality also increases for getting out of local minimum and converge to the global minimum of cost for the global maximum of quality. If no trade-off is found, we modify the quality contracts (i.e. we soften the constraints) and restart the process with new costs and new qualities. The algorithm starts from a valid solution and randomly generates new states, for the problem and calculates the associated cost and quality function. Simulation of the annealing process starts at high fictitious temperature (noted T). A new state is randomly chosen and the differences in cost and in quality function are calculated. If ∆ Cost ≤ 0, i.e., the cost is lower and the quality is monotone or increasing, then this new state is accepted. This forces the system toward a state corresponding to a local or a possibly a global minimum. However, most large optimization problems have many local minima and the optimization algorithm is therefore often trapped in a local minimum. To get out of a local minimum, an increase of the cost function is accepted with a certain probability. For each temperature, the system must reach the equilibrium i.e., a number of new states must be tried before the temperature is reduced typically by 10 %. It can be shown that the algorithm will find, under certain condition, the global minimum and not get stuck in local minima. The source that provides the trade-off is selected for answering the query.

Proceedings of the Ninth International Conference on Information Quality (ICIQ-04)

A SIMPLE EXAMPLE

Consider a list of queries sent to four overlapping sources with five attributes A1, …, A5 (see the structure of the sources in Table 1). Consider ten quality dimensions (d1, …, d10) previously defined in Figure (1a) for Reliability, Freshness, Completeness and Credibility contract types. Each query (listed in Table 2) is extended with the following quality statement: query# Qwith quality for Source_Set = profile {require Reliability, Freshness, Completeness, Credibility}; with query# the variable representing the query number in Table 2 andSource_Set={S1 S e le c t(A 1 , λ a 1 , tru e ) S 1 ,S 2 ,S 3 ,S 4 s 1 q 2 S e le c t(A 2 , λ a 2 , a 2 > 3 0 ) S 1 ,S 2 ,S 3 ,S 4 s 4 q 3 P ro je c t(A 3 , λ a 3 , J o in ( q 1 ,q 2 , λ a 1 , a 2 , (a 1 = a 2 )) )

S o u r c e s A t t r ib u te s S 1

A 1 A 2 A 3 A 4 S 2 A 1 A 2 A 3 A 4 S 3 A 1 A 2 < 5 0 A 4 S 4 A 1 A 2 > 4 0 A 3 Q u e
S 1 ,S 2 ,S 4 S 2 q 4 P ro je c t(A 4 , λ a 4 , J o in ( q 1 ,q 2 , λ a 1 , a 2 , (a 1 = a 2 )) )

S 1 ,S 2 ,S 3 S 1

Table 1. Source schema

Table 2. List of queries and their corresponding costs

For each query, the negotiation processing computes the trade-off that minimizes the query cost and maximizes the quality over the four sources with eventually renegotiating quality contracts to find the best trade-off.

For this example, as illustrated in Figure 6, starting in state i, the new state k1 (provided by source S4) is accepted, but the new state k2 (provided by source S1) is only accepted with a certain probability.

The probability of accepting a worse state is high at the beginning and decreases at the temperature decreases. Finally the global minimum of trade-off is found and is provided by source S1 that will be queried first. Proceedings of the Ninth International Conference on Information Quality (ICIQ-04)

CONCLUSION

We propose XQuaL, a query language extension including declarations of quality contracts and profiles and we present the algorithm of quality-driven negotiation for adaptive query processing. Our negotiator module is fully implemented and preliminary performance experiments are ongoing.

The contribution of this work is twofold. Firstly, we propose a declarative language for specifying and querying data as well as quality metadata: we take advantage of QML [START_REF] Frølund | QML: A Language for Quality of Service Specification[END_REF] in the domain of Quality of Service for flexibly extending our query language with constraints on quality of service and on quality of distributed data sources. Secondly, past work on query processing has largely ignored the issue of source quality negotiation and trade-offs between query costs and result quality gains: our approach introduces trade-offs into the query processing considering the multi-dimensional quality aspect.

Our current work is focused on the definition of appropriate database statistics and a cost model, and we describe plan enumeration including heuristics and different strategies for quality negotiation. In most of the real world, it is quite natural that quality-extended query should meet a number of different and conflicting quality dimensions. Optimizing a particular objective function may sacrifice optimization of another dependent and conflicting objective. The purpose of our future work is to study the quality-adaptive query processing problem from the perspective of multi-objective optimization.

  Figure (1b) shows their corresponding contract instances. The type of the Reliability contract has four dimensions (noted d1, …, d4 as comments of Figure (1a)), named respectively failureMasking, serverFailure, numberOfFailures and availability. Dimension failureMasking is Proceedings of the Ninth International Conference on Information Quality (ICIQ-04)defined by the possible values among omission, lostResponse, noExecution, etc. and the relation (decreasing) is interpreted such as the smallest sets of values are the preferable values for this dimension. Dimension serverFailure is defined by individual values named without order. Dimensions numberOfFailures and availability are numerical dimensions. nf/year is the number of failures per year as a unit of numberOfFailures.

Figure

  Figure (1b) presents four instances of these contract types for the source S1 such as: S1_Reliability, S1_Freshness, S1_Completeness, and S1_Credibility.

Figure 3 .

 3 Figure 3. Example of source profile for Source S1

Figure 4a .

 4a Figure 4a. Quality for sources S1, S2, S3 and S4 Figure 4b. Query costs over S1, S2, S3 and S4

Figure 5 .

 5 Figure 5. Pseudocode for Negotiation

  ,S2,S3,S4}. The quality of the four sources is given in Figure (4a) over the ten dimensions. Their costs are given in Figure (4b) from the initial time of the query T0.

  r y # A lg e b r a ic E x p r e s s io n C a n d id a te S o u r c e s B e s t S o u r c e q 1

Figure 6 .

 6 Figure 6. Reaching the global minimum trade-off for the quality-extended query q1

2.1. Quality of Service

	Proceedings of the Ninth International Conference on Information Quality (ICIQ-04)
	Quality of service (QoS) has gained much attention in the field of distributed multimedia applications
	where it covers essentially the notion of end-to-end guarantees associated with the communication of
	multimedia contents over networks and their processing on computing nodes. A considerable amount
	of work has been done in this area to introduce models and architectures supporting such QoS
	guarantees. This narrow vision of QoS (generally centered on the concept of performance) is currently
	generalized to extra-functional properties of distributed systems [10][1]. The traditional acceptance of
	quality of service for distributed information systems has been recently revised with a broader

Proceedings of the Ninth International Conference on Information Quality (ICIQ-04)

APPENDICES: SYNTAX OF XQUAL


Out of Overinformation by Information Filtering and

Information Weighting


published or not. The documents may come


Thierry Urruty

Fatima Belkouch

Chaabane Djeraba

Dan A Simovici

Rpyr

RPyR : Nouvelle Structure d'Indexation avec Classification par Projections Aléatoires

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Jean-Louis Merrien
email: jmerrien@insa-rennes.fr

Tomas Sauer
email: tomas.sauer@uni-passau.de

Generalized Taylor operators, polynomial chains, and Hermite subdivision schemes

Keywords:

Hermite subdivision schemes act on vector valued data that is not only considered as functions values of a vector valued function from R to R r , but as evaluations of r consecutive derivatives of a function. This intuition leads to a mild form of level dependence of the scheme. Previously, we have proved that a property called spectral condition or sum rule implies a factorization in terms of a generalized difference operator that gives rise to a "difference scheme" whose contractivity governs the convergence of the scheme. But many convergent Hermite schemes, for example, those based on cardinal splines, do not satisfy the spectral condition. In this paper, we generalize the property in a way that preserves all the above advantages: the associated factorizations and convergence theory. Based on these results, we can include the case of cardinal splines in a systematic way and are also able to construct new types of convergent Hermite subdivision schemes.

Introduction

Subdivision schemes, as established in [START_REF] Cavaretta | Stationary Subdivision[END_REF], are efficient tools for building curves and surfaces with applications in design, creation of images and motion control. For vector subdivision schemes, cf. [START_REF] Dyn | Subdivision schemes in geometric modelling[END_REF][START_REF] Han | Vector cascade algorithms and refinable functions in sobolev spaces[END_REF][START_REF] Micchelli | On vector subdivision[END_REF], it is not so straightforward to prove more than the Hölder regularity of the limit function, due to the more complex nature of the underlying factorizations. On the other hand, Hermite subdivision schemes [START_REF] Dyn | Analysis of Hermite-type subdivision schemes[END_REF][START_REF] Han | Design of Hermite subdivision schemes aided by spectral radius optimization[END_REF][START_REF] Han | Noninterpolatory Hermite subdivision schemes[END_REF][START_REF] Jeong | Construction of Hermite subdivision schemes reproducing polynomials[END_REF][START_REF] Guglielmi | Convergence analysis of C 2 Hermite interpolatory subdivision schemes by explicit joint spectral radius formulas[END_REF] produce function vectors that consist of consecutive derivatives of a certain function, so that the notion of convergence automatically includes regularity of the leading component of the limit. Such schemes have even been considered also on manifolds recently [START_REF] Moosmüller | C 1 analysis of Hermite subdivision schemes on manifolds[END_REF] and have also been used for wavelet constructions [START_REF] Cotronei | A note on Hermite multiwavelets with polynomial and exponential vanishing moments[END_REF]. While vector subdivision schemes are quite well-understood, nevertheless there are still surprisingly many open questions left in Hermite subdivision. In particular, a characterization of convergence in terms of factorization and contractivity is still missing as it is known in the scalar case: a subdivision scheme is convergent if and only if it can be factorized by means of difference operators and the resulting difference scheme is contractive.

In previous papers [START_REF] Dubuc | Hermite subdivision schemes and Taylor polynomials[END_REF][START_REF] Merrien | From Hermite to stationary subdivision schemes in one and several variables[END_REF][START_REF] Merrien | Extended Hermite subdivision schemes[END_REF], we established an equivalence between a so-called spectral condition and operator factorizations that transform a Hermite scheme into a vector scheme for which analysis tools are available. Under this transformation, the usual convergence of the vector subdivision scheme implies convergence for the Hermite scheme and thus regularity of the limit function. It was even conjectured for some time that the spectral condition, sometimes also called the sum rules [START_REF] Conti | Approximation order and approximate sum rules in subdivision[END_REF][START_REF] Han | Noninterpolatory Hermite subdivision schemes[END_REF] of the Hermite subdivision scheme, might be necessary for convergence. Already in [START_REF] Merrien | A generalized Taylor factorization for Hermite subdivisions schemes[END_REF] this was relaxed to some extent by considering proper similarity transforms of the mask that gave slightly generalized sum rules.

In this paper we show, among others results, that this conjecture does not hold true. We define a new set of significantly more general spectral conditions, called spectral chains, that widely generalize the classical spectral condition from [START_REF] Dubuc | Hermite subdivision schemes and Taylor polynomials[END_REF] and show that these spectral conditions are more or less equivalent to the existence of a factorization with respect to respective generalized Taylor operators and allow for a description of convergence by means of contractivity. Indeed, we conjecture that these factorization can be used to eventually characterized the convergence of Hermite subdivision schemes by means of contractive different schemes. We then define a process that allows us to construct Hermite subdivision schemes of arbitrary regularity with guaranteed convergence and, in particular, give examples of convergent Hermite subdivision schemes that do not satisfy the spectral condition. In addition, our new method can be applied to an example based on B-splines and their derivatives which was one of the first examples of a convergent Hermite subdivision scheme that does not satisfy the spectral condition, [START_REF] Merrien | A generalized Taylor factorization for Hermite subdivisions schemes[END_REF].

The paper is organized as follows: after introducing some basic notation and the concept of convergent vector and Hermite subdivision schemes, we introduce the new concept of chains and generalized Taylor operators in Section 4 and use them for the factorization of subdivision operators in Section 4. These results allow us to extend the known results about the convergence of the Hermite subdivision schemes to this more general case in Section 5. Section 6 is devoted to the construction of a convergent Hermite subdivision scheme emerging from a properly constructed contractive vector subdivision scheme by reversing the factorization process, even in the generality provided by generalized Taylor operators. Finally, we give some examples of the results of such constructions in Section 7, and also provide a new approach for the aforementioned spline case.

Notation and fundamental concepts

Vectors in R r , r ∈ N, will generally be labeled by lowercase boldface letters: y = y j j =0,...,r -1 or y = y ( j ) j =0,...,r -1 , where the latter notation is used to highlight the fact that in Hermite subdivision the components of the vectors correspond to derivatives. Matrices in R r ×r will be written as uppercase boldface letters, such as A = a j k j ,k=0,...,r -1 . The space of polynomials in one variable of degree at most n will be written as Π n , with the usual convention Π -1 = {0}, while Π will denote the space of all polynomials. Vector sequences will be considered as functions from Z to R r and the vector space of all such functions will be denoted by ℓ(Z, R r ) or ℓ r (Z). For y(•) ∈ ℓ(Z, R r ), the forward difference is defined as ∆y(α) := y(α+1)-y(α), α ∈ Z, and iterated to ∆ i +1 y := ∆ ∆ i y = ∆ i y(• + 1) -∆ i y(•), i ≥ 0.

We use 0 to indicate zero vectors and matrices. If we want to highlight the dimension of the object, we will use subscript 0 d , but to avoid too cluttered notation, we will often drop them if the size of the object is clear from the context. Moreover, we will use the convenient Matlab notation A j : j ′ ,k:k ′ and a j : j ′ to denote submatrices and subvectors.

Given a finitely supported sequence of matrices A = (A(α)) α∈Z ∈ ℓ r ×r (Z), called the mask of the subdivision scheme, we define the associated stationary subdivision operator

S A : c → β∈Z A(• -2β) c(β), c ∈ ℓ r (Z).
The iteration of subdivision operators S A n , n ∈ N, is called a subdivision scheme and consists of the successive applications of level-dependent subdivision operators, acting on vector valued data, S A n : ℓ r (Z) → ℓ r (Z), defined as

c n+1 (α) = S A n c n (α) := β∈Z A n α -2β c n (β), α ∈ Z, c ∈ ℓ r (Z) . (1)
An important algebraic tool for stationary subdivision operators is the symbol of the mask, which is the matrix valued Laurent polynomial

A * (z) := α∈Z A(α) z α , z ∈ C \ {0}. (2)
We will focus our interest on two kinds of such schemes, the first one being "traditional" vector subdivision schemes in the sense of [START_REF] Cavaretta | Stationary Subdivision[END_REF], where A n is independent of n, i.e., A n (α) = A(α) for any α ∈ Z and any n ≥ 0. In the following, such schemes for which an elaborate theory of convergence exists, will simply be called a vector scheme. Their convergence is defined in the following way.

Definition 1

Let S A : ℓ r (Z) → ℓ r (Z) be a vector subdivision operator. The operator is C pconvergent, p ≥ 0, if for any data g ∈ ℓ r (Z) and corresponding sequence of refinements g n = S n A g , g 0 := g , there exists a function ψ g ∈ C p (R, R r ) such that for any compact K ⊂ R there exists a sequence ε n with limit 0 that satisfies

max α∈Z∩2 n K g n (α) -ψ g 2 -n α ∞ ≤ ε n . (3)
As the second type of, now even level-dependent, schemes we consider the Hermite scheme

where A n (α) = D -n-1 A(α)D n for α ∈ Z and n ≥ 0 with the diagonal matrix D :=       1 1 2 . . . 1 2 d       .
In this case r = d + 1 and for k = 0, . . . , d the k-th component of c n (α) corresponds to an approximation of the k-th derivative of some function ϕ n at α2 -n . Starting from an initial sequence c 0 , a Hermite scheme can be rewritten

D n+1 c n+1 (α) = D n+1 S A D n c n (α) = β∈Z A α -2β D n c n (β), α ∈ Z, n ≥ 0. ( 4
)
Convergence of Hermite schemes is a little bit more intricate and defined as follows.

Definition 2 Let A ∈ ℓ (d +1)×(d +1) (Z) be a mask and H A the associated Hermite subdivision scheme on ℓ d +1 (Z) as defined in (4). The scheme is convergent if for any data f 0 ∈ ℓ d +1 (Z) and the corresponding sequence of refinements

f n = [ f (0) n , . . . , f (d ) n ] T , there exists a function Φ = [φ i ] 0≤i ≤d ∈ C R, R d +1
such that for any compact K ⊂ R there exists a sequence ε n with limit 0 which satisfies max 0≤i ≤d max

α∈Z∩2 n K f (i ) n (α) -φ i 2 -n α ≤ ε n . ( 5
)
The scheme H A is said to be C p -convergent with p ≥ d if moreover φ 0 ∈ C p (R, R) and

φ (i ) 0 = φ i , 0 ≤ i ≤ d .

Remark 3 Since the intuition of Hermite subdivision schemes is to iterate on function values

and derivatives, it usually only makes sense to consider C p -convergence for p ≥ d . Note, however, that the case p > d leads to additional requirements.

The (classical) spectral condition of a subdivision operator has been introduced in [START_REF] Dubuc | Hermite subdivision schemes and Taylor polynomials[END_REF]. It requests that there exist polynomials p j ∈ Π j , j = 0, . . . , d , such that

S A       p j p ′ j . . . p (d ) j       = 2 -j       p j p ′ j . . . p (d ) j       , j = 0, . . . , d . (6)
This spectral condition is a special case of a spectral chain that will be defined in Definition 21.

Generalized Taylor operators and chains

In this section, we introduce the concept of generalized Taylor operators and show that they form the basis of symbol factorizations. The first definition concerns vectors of almost monic polynomials of increasing degree.

Definition 4 By V d we denote the set of all vectors v of polynomials in Π d with the property that

v =    v d . . . v 0    , v j = 1 j ! (•) j + u j ∈ Π j , u j ∈ Π j -1 . (7)
A vector in V d thus consists of polynomials v j of degree exactly j whose leading coefficient is normalized to 1 j ! , and the remaining part of the polynomial v j of lower degree is denoted by u j .

Note that in [START_REF] Dyn | Analysis of Hermite-type subdivision schemes[END_REF] we always have v 0 = 1 and u 0 = 0. Also keep in mind that the vectors v are indexed in a reversed order, but referring directly to the degree of the object, this notion is more comprehensible.

We will use the convenient notation of Pochhammer symbols (•) j ∈ Π j , j ≥ 0, in the following way:

(•) 0 := 1, (•) j := j -1 k=0 (• -k), j ≥ 1, and [•] j := 1 j ! (•) j , j ≥ 0. ( 8
)
These polynomials satisfy

∆(•) j = j (•) j -1 , ∆[•] j = [•] j -1 . (9)
Both (•) 0 , . . . , (•) j and [•] 0 , . . . , [•] j are bases of Π j and allow us to write the Newton interpolation formula of degree d at 0, . . . , d in the form

x j = j k=0 1 k! ∆ k (•) j (0) (x) k = j k=0 ∆ k (•) j (0) [x] k ;
then, since ∆ j (•) j = j !, we have that

1 j ! (•) j = [•] j + j -1 k=0 ∆ k (•) j (0) j ! [x] k which implies that v ∈ V d ⇔ v j = [•] j + u j , u j ∈ Π j -1 j = 0, . . . , d . (10)
We will use this form in the future to write each v ∈ V d as

v =    [•] d . . . [•] 0    + u. ( 11
)
Generalizing the Taylor operators operating on vector functions R → R d +1 introduced in [START_REF] Dubuc | Hermite subdivision schemes and Taylor polynomials[END_REF][START_REF] Merrien | From Hermite to stationary subdivision schemes in one and several variables[END_REF], we define the following concept.

Definition 5 A generalized incomplete Taylor operator is an operator of the form

T d :=          ∆ -1 * . . . * . . . . . . . . . . . . . . . . . . * ∆ -1 1          = ∆I 1 + t j k j ,k=0,...,d , (12)
where t j , j +1 = -1 and t j k = 0 for k ≤ j . In the same way, the generalized complete Taylor operator is of the form Proof: For "⇐" suppose that T d v = 0 and let us prove by induction on j = 0, . . . , d that v j = [•] j + u j for some appropriate u j ∈ Π j -1 . The assumption v 0 = 1 ensures that for j = 0 by simply setting u 0 = 0. Now, for 0 ≤ j < d , we assume that v j +1 is of degree m ≥ 0 and write it in the basis {[•] 0 , . . . , [•] m } as

T d :=          ∆ -
v j +1 = m k=0 c k [•] k = m k= j +2 c k [•] k + c j +1 [•] j +1 + q,
with q ∈ Π j , hence ∆q ∈ Π j -1 . By induction hypothesis, we have that

v j = [•] j + u j , u j ∈ Π j -1 and v k ∈ Π k for k = 0, . . . , j -1. Then T d v = 0 implies at row d -j -1 that 0 = ∆v j +1 -v j + j -1 k=0 t d -j -1,d -k v k = m k= j +2 c k [•] k-1 + c j +1 [•] j + ∆q -[•] j -u j + j -1 k=0 t d -j -1,d -k v k = m-1 k= j +1 c k+1 [•] k + c j +1 -1 [•] j + u, u ∈ Π j -1 ,
and comparison of coefficients yields c j +2 = • • • = c m = 0 as well as c j +1 = 1, hence v j +1 = [•] j +1 + u j +1 with u j +1 ∈ Π j , which advances the induction hypothesis. For the converse "⇒", we note that for any v ∈ V d we have that for j ≥ 1

∆v j -v j -1 = [•] j -1 + ∆u j -[•] j -1 -u j -1 = ∆u j -u j -1 ∈ Π j -2
and since v 0 , . . . , v j -2 is a basis of Π j -2 , the polynomial ∆v j -v j -1 can be uniquely written as

c 0 v 0 + • • • + c j -2 v j -2 = - d ℓ=d -j +2 t d -j ,ℓ v d -ℓ
which defines the remaining entries of row d -j of T d in a unique way such that

T d v = 0.
The last observation in the above proof can be formalized as follows.

Corollary 8 For each v ∈ V d there exists a unique generalized complete Taylor operator T d such that T d v = 0.

Definition 9

The generalized Taylor operator of Corollary 8, uniquely defined by

T (v ) v = 0, ( 14
)
is called the annihilator of v ∈ V d and written as T (v ). We can skip the subscript "d " because it is directly given by the dimension of v .

Definition 10 A chain of length d + 1 is a finite sequence V := [v 0 , . . . , v d ] of vectors v j =    v j , j . . . v j ,0    =    [•] j . . . [•] 0    + u j ∈ V j , j = 0, . . . , d ,
that satisfies the compatibility condition

w j +1 :=    w j +1,1 . . . w j +1, j +1    := T (v j )    v j +1, j +1 . . . v j +1,1    ∈ R j +1 , j = 0, . . . , d -1. ( 15
)
Remark 11 Compatibility is a strong requirement on the interaction between v j and v j +1 . In

general, T (v j )    v j +1, j +1 . . . v j +1,1
   can only be expected to be a vector of polynomials in Π j , . . . , Π 0 , while compatibility requires all these polynomials to be constants.

Due to and by means of the compatibility condition, chains uniquely define a generalized Taylor operator.

Lemma 12

If V is a chain of length d + 1, then w j j = 1, j = 1, . . . , d .

Proof: Since v j +1,1 = [•] 1 + c for some constant c due to v j ∈ V j , it follows immediately from the definition (15) that w j +1, j +1 = ∆v j +1,1 = 1, as claimed.

We introduce the convenient abbreviation

v j := v j 0 d -j ∈ R d +1 , j = 0, . . . , d , (16)
where the dimension d is clear from the context.

Proposition 13

For V = [v 0 , . . . , v d ], v j ∈ V j , j = 0, . . . , d , of length d + 1 the following statements are equivalent:

1. V is a chain of length d + 1.
2. For j = 1, . . . , d , we have

T (v j ) = T (v j -1 ) -w j ∆ =        ∆ -w 1,1 . . . -w j ,1 ∆ . . . . . . . . . -w j , j ∆        , w j ∈ R j . ( 17
)
3.

T (v d ) v j = 0, j = 0, . . . , d .

Proof: To show that 1) ⇒ 2), we note that again [START_REF] Merrien | From Hermite to stationary subdivision schemes in one and several variables[END_REF] yields that

0 = T (v j )    v j +1, j +1 . . . v j +1,1    -w j +1 = T (v j ) | -w j +1       v j +1, j +1 . . . v j +1,1 1
      = T (v j ) | -w j +1 v j +1 .
Since T (v j +1 ) is unique, we deduce that

T (v j +1 ) = T (v j ) -w j +1 ∆ , j = 0, . . . , d -1, (19)
which directly yields [START_REF] Micchelli | Mathematical Aspects of Geometric Modeling[END_REF].

For 2) ⇒ 3) we simply notice that

T (v d ) v j = T (v j ) * 0 * v j 0 d -j = T (v j )v j 0 = 0, while for 3) ⇒ 1) we first observe for j < d that 0 = T (v d ) v j = T (v d ) 0: j ,0: j v j 0
and the uniqueness of the annihilators from Corollary 8 yields that T (v d ) 0: j ,0: j = T (v j ). This, in turn, implies together with [START_REF] Micchelli | On vector subdivision[END_REF] that

0 = T (v d ) v j +1 =   T (v j ) -w j +1 * ∆ * *           v j +1, j +1 . . . v j +1,1 1 0         =         T (v j )    v j +1, j +1 . . . v j +1,1    -w j +1 0 0        
, which is the compatibility identity (15), hence V is a chain.

The above proof shows that T (v j ) = T (v d ) 0: j ,0: j , j = 0, . . . , d , hence all generalized Taylor operators associated to a chain depend only on v d . This justifies the following definition.

Definition 14

The unique generalized Taylor operator T (v d ) for a chain V will be written as T (V ).

Remark 15 Since complete and incomplete

Taylor operators differ only on the ∆ or 1 in lower right corner, there is an obvious extension of the definition to T (V ) and the two operators are equivalent.

Example 16 Let p j = [•] j + q j , q j ∈ Π j -1 , j = 0, . . . , d , be given. Then

v j = p j , p ′ j , . . . , p ( j ) j T is a chain for the classical complete Taylor operator T C ,d :=            ∆ -1 -1/2! -1/3! . . . -1/d ! ∆ -1 -1/2! . . . -1/(d -1)! ∆ -1 . . . . . . . . . . . . ∆ -1 ∆            . ( 20
)
This is exactly the relationship for the classical spectral condition from [START_REF] Dubuc | Hermite subdivision schemes and Taylor polynomials[END_REF][START_REF] Merrien | From Hermite to stationary subdivision schemes in one and several variables[END_REF]. Similarly,

v j = p j , ∆p j , . . . , ∆ j p j T is a chain for the operator T ∆,d :=        ∆ -1 0 . . . . . . . . . -1 ∆        . ( 21
)
Another interesting generalized Taylor operator is

T S,d :=        ∆ -1 . . . -1 . . . . . . . . . . . . -1 ∆        , ( 22
)
whose chains, connected to B-splines, we will consider in Example 46 later.

Lemma 17 For any generalized complete Taylor operator T d there exists a chain

V of length d + 1 such that T d = T d (V ).
Proof: The construction of the chain V is carried out inductively. To that end, we recall that if

p ∈ Π is of the form ∆p = [•] k for some k ∈ N, then p = [•] k+1 + c with some c ∈ R. Next, let v j ∈ V j , j = 0, . . . , d , be any solution of 0 = T d v j = T j * 0 * v j 0 d -j ,
or, equivalently, of T j v j = 0. Such a solution can be found by setting v j 0 = 1 and then solving, recursively for k = 1, . . . , j , the equation given by row j -k of the Taylor operator,

0 = ∆v j ,k -v j ,k-1 + k-2 ℓ=0 t j -k, j -ℓ v j ,ℓ . (23)
Equivalently, this can be written with respect to the basis {

[•] 0 , . . . , [•] k-1 } and using v j ,k-1 = [•] k-1 + u j ,k-1 , u j ,k-1 ∈ Π k-2 , as 0 = ∆v j ,k -[•] k-1 + k-2 ℓ=0 s j -k,ℓ [•] ℓ , s j -k,ℓ ∈ R, yielding v j k = [•] k + k-1 ℓ=1 s j -k,ℓ-1 [•] ℓ + c k0 , k = 0, . . . , j ,
where the constants c k0 ∈ R can be chosen freely. This process yields polynomial vectors v j ∈ V j such that T j v j = 0, j = 0, . . . , d . Thus, it follows from the uniqueness of the annihilating Taylor operator from Corollary 8 that T j = T (v j ), and decomposing the identity

0 = T (v j +1 )v j +1 = T j +1 v j +1 = T (v j ) -w 0 ∆ v j +1 , w ∈ R j +1 , yields T (v j )    v j +1, j +1 . . . v j +1,1    = w =: w j +1 , (24)
which is exactly the compatibility condition [START_REF] Merrien | From Hermite to stationary subdivision schemes in one and several variables[END_REF] needed for V to be a chain.

Corollary 18

In the chain V from Lemma 17 the constant coefficients of the polynomials v j k , j = 1, . . . , d , k = 1, . . . , j , can be chosen arbitrarily.

Remark 19

The chain associated to a generalized Taylor operator is not at all unique, see also Example 16.

The next result shows that any polynomial vector in V d can be reached by a chain of length d + 1.

Proposition 20 For any

v ∈ V d there exists a chain V = [v 0 , . . . , v d ] of length d +1 with v d = v , i.e., T (V ) = T (v ).
Proof: Again we prove the claim by induction on d . The case d = 0 is trivial as the only chain of length 0 consists of v = 1. For the induction step, we choose v ∈ V d , d > 0 and the associated generalized Taylor operator T (v ) as in Definition 9. Then we know from Lemma 17 that there exists a chain

V = [v 0 , . . . , v d ] of length d + 1 such that T (v )V = 0. Suppose that v d = v and, in particular, that v d ,1 (0) = v 1 (0) -1, which is possible according to Corollary 18. With v =    [•] d . . . [•] 0    + u, v d =    [•] d . . . [•] 0    + u d , u 0 = u d ,0 = 0, we find that 0 = T (v ) (v -v d ) = T (v )       u d -u d ,d . . . u 1 -u d ,1 0       =: T (v ) v ′ 0 where u 1 -u d ,1 = v 1 (0) -v d ,1 (0) = 1.
In addition, Lemma 7 yields that v ′ ∈ V d -1 and therefore the decomposition

T (v ) = T (v ′ ) -w 0 ∆ , w ∈ R d ,
and

0 = T (v )v = T (v ′ ) -w 0 ∆       v d . . . v 1 1       =         T (v ′ )       v d . . . v 1 1       -w ∆        
compatibility between v ′ and v . By the induction hypothesis, there exists a chain V ′ of length

d with v d -1 = v ′ and since v ′ is compatible with v , this chain can be extended to length d + 1 with v ′ d = v .

Chains and factorizations

We now relate the existence of a spectral chain to factorizations of the subdivision operators, thus extending the results first given in [START_REF] Merrien | From Hermite to stationary subdivision schemes in one and several variables[END_REF] for the classical Taylor operator.

Definition 21 A chain V of length d +1 is called spectral chain for a vector subdivision scheme with mask

A ∈ ℓ (d +1)×(d +1) (Z) if S A v j = 2 -j v j , j = 0, . . . , d . ( 25
)
with v j from [START_REF] Merrien | Extended Hermite subdivision schemes[END_REF].

Remark 22

The spectral chain is an extension of the classical spectral condition which, in turn, corresponds to the special choice v j = p j , p ′ j , . . . , p (d ) j T , see also Example 16.

We will prove in Theorem 25 that the existence of spectral chains is equivalent to the existence of generalized Taylor factorizations. The main tool for this proof is the following result.

Proposition 23 If C ∈ ℓ (d +1)×(d +1) (Z)
is a finitely supported mask for which there exists a chain V such that S C v j = 0, j = 0, . . . , d , then there exists a finitely supported mask B ∈ ℓ

(d +1)×(d +1) (Z) such that S C = S B T (V ).
Proof: We follow the idea from [START_REF] Merrien | From Hermite to stationary subdivision schemes in one and several variables[END_REF] and prove by induction on k that the symbol C * (z) satisfies

C * (z) = B * k (z) T (v k ) * (z 2 ) 0 0 I , k = 0, . . . , d . ( 26
)
with the columnwise written matrix

B * k (z) = b * 0 (z) • • • b * k (z) c * k+1 (z) • • • c * d (z) . ( 27
)
The construction makes repeated use of the well known factorization for a scalar subdivision scheme S a :

α∈Z a(α -2β) = 0 ⇒ a * (z) = (z -2 -1)b * (z), (28)
see, for example, [START_REF] Cavaretta | Stationary Subdivision[END_REF] for a proof.

For case k = 0, the annihilation of the vector v 0 = e 0 = [1, 0, . . . , 0] T immediately gives the decomposition c * 0 (z) = z -2 -1 b * 0 (z) and therefore

C * (z) = b * 0 (z) c * 1 (z) • • • c * d (z) z -2 -1 I = b * 0 (z) c * 1 (z) • • • c * d (z) T (v 0 ) * (z 2 ) I .
Now suppose that (26) holds for some k ≥ 0. Then the fact that V is a chain yields, by means of the compatibility condition

w k+1 = T (v k )    v k+1,k+1 . . . v k+1,1    that 0 = S C v k+1 = S B k   T (v k ) 1 I   v k+1 0 = S B k   w k+1 1 0   ,
or, applying (28) to each row of the preceding equation,

b * 0 (z) • • • b * k (z) T w k+1 + c * k+1 (z) = z -2 -1 b * k+1 (z), which is c * k+1 (z) = b * 0 (z) • • • b * k+1 (z) T -w k+1 z -2 -1 , or C * (z) = b * 0 (z) • • • b * k+1 (z) c * k+2 (z) • • • c * d (z)   T (v k ) * (z 2 ) -w k+1 z -2 -1 I   . ( 29
)
Since

T (v k+1 ) * (z) = T (v k ) * (z) -w k+1 z -1 -1 ,
(29) yields (26) with k replaced by k + 1 and advances the induction hypothesis.

Remark 24 Proposition 23 shows that, in the terminology of [START_REF] Conti | Hermite subdivision schemes, exponential polynomial generation, and annihilators[END_REF], the generalized Taylor operator is a minimal annihilator for the chain V since it annihilates the chain and factors any subdivision operator that does so, too.

Now we can show that the existence of a spectral chain results in the existence of a factorization by means of generalized Taylor operators. Since the Taylor operator corresponds to computing differences, the scheme S B from (30) is often called the difference scheme of S A with respect to the generalized Taylor operator T (V ).

Theorem 25 If S A possesses a spectral chain V of length d + 1 then there exists a finite mask

B ∈ ℓ (d +1)×(d +1) (Z) such that T (V ) S A = S B T (V ). ( 30
)
Proof: Since S C := T (V )S A has the property that

S C v k = T (V )S A v k = 2 -k T (V )v k = 0,
an application of Proposition 23 proves the claim.

Remark 26 For the validity of Theorem 25, which is of a purely algebraic nature, the concrete eigenvalues of the spectral set are irrelevant. Their normalization will play a role, however, as soon as convergence is concerned.

Next, we generalize a result from [START_REF] Merrien | Extended Hermite subdivision schemes[END_REF] that serves as a converse of Theorem 25. The proof is a modification of the former.

Theorem 27 Suppose that for a finitely supported mask A ∈ ℓ (d +1)×(d +1) there exists a finitely supported B and a generalized incomplete Taylor operator T d such that

T d S A = 2 -d S B T d and S B e d = e d . If a chain V = [v 0 , . . . , v d ] with T d = T (V ) satisfies S A v j ∈ span v 0 , . . . , v j , j = 0, . . . , d , (31)
then there exists a spectral chain V ′ for S A .

Proof: Relying on Lemma 17, we choose a chain V such that T d = T (V ), which particularly yields that

T d v d = e d .
Then

T d v d = e d = S B e d = S B T d v d = 2 d T d S A v d implies that T d 2 -d v d -S A v d = 0, hence S A v d = 2 -d v d + ṽ , 0 = T d ṽ = T d -1 * 1 ṽ ,
so that ṽ0 = 0 and therefore T d -1 v 0:d -1 = 0. Since v 0 , . . . , v d -1 form a basis for the kernel of T d with last component equal to zero, it follows that v ∈ span{ v 0 , . . . , v d -1 }. Making use of the two-slantedness of S A , one can literally repeat the arguments of the proof of [16, Theorem 2.11] to conclude that

S A v j -2 -j v j ∈ span v 0 , . . . , v j -1 , hence S A [ v 0 , . . . , v d ] = [ v 0 , . . . , v d ]U , where U ∈ R (d +1)×(d +1
) is an upper triangular matrix with diagonal entries 1, . . . , 2 -d . Using the upper triangular S such that S -1 U S is diagonal, we can then define

V ′ by v ′ 0 , . . . , v ′ d = [ v 0 , . . . , v d ] S, which is a chain since T (v d ) j k=0 c k v k = 0, j = 0, . . . , d ,
due to Proposition 13.

Convergence

From [START_REF] Merrien | From Hermite to stationary subdivision schemes in one and several variables[END_REF][START_REF] Merrien | Extended Hermite subdivision schemes[END_REF] we know that the Hermite subdivision scheme H A converges to a Note that the normalization with the factor 2 -d now becomes relevant since it affects the normalization and contractivity property of S B and S B , respectively. Before we give the results about the convergence replacing T C ,d and T C ,d by T and T , respectively, we will now consider conditions to guarantee that B is the result of such a factorization. To that end, we recall the factorization identity

I d ∆ S B = S B I d ∆ (32)
from vector subdivision [START_REF] Micchelli | On vector subdivision[END_REF]. This relationship does not depend on the form of the Taylor operator. In terms of symbols, (32) becomes

I d z -1 -1 B * 11 (z) B * 12 (z) B * 21 (z) B * 22 (z) = B * 11 (z) B * 12 (z) B * 21 (z) B * 22 (z) I d z -2 -1 , (33)
hence

B * (z) = I d z -1 -1 -1 B * 11 (z) B * 12 (z) B * 21 (z) B * 22 (z) I d z -2 -1 = B * 11 (z) (z -2 -1) B * 12 (z) (z -1 -1) -1 B * 21 (z) (z -1 + 1) B * 22 (z) . ( 34
)
Lemma 28 S B converges to a continuous limit function of the form ψ g = f g e d if and only if S B is contractive, B 21 (1) = 0 and B 22 (1) = 1.

Proof: That convergence of the above type is equivalent to factorization and contractivity has been shown in [START_REF] Micchelli | On vector subdivision[END_REF], which already gives "⇒". For "⇐", however, we also must ensure that B * as defined in (34) is a Laurent polynomial. To that end, we must have B *

Lemma 30 Given a sequence of refinements h

n = h (0) n h (1) n ∈ ℓ(Z, R 2 ) such that 1. there exists a constant c in R such that lim n→+∞ h (0) n (0) = c,
2. there exists a function ξ ∈ C (R, R) such that for any compact subset K of R there exists a sequence µ n with limit 0 and max

α∈2 n K ∩Z h (1) n (α) -ξ 2 -n α ∞ ≤ µ n , (35)
max

α∈2 n K ∩Z 2 n ∆h (0) n (α) -h (1) n (α) ∞ ≤ µ n . ( 36
)
Then there exists for any compact K a sequence θ n with limit 0 such that the function

ϕ(x) = c + 1 0 x ξ (t x) d t , x ∈ R, (37)
satisfies max Suppose that for any initial data f 0 ∈ ℓ d +1 (Z) and associated refinement sequence f n of the Hermite scheme H A , 1. the sequence f n (0) converges to a limit y ∈ R d +1 , 2. the subdivision scheme S B is C p-d -convergent for some p ≥ d , and that for any initial data g 0 = T d f 0 , the limit function

α∈2 n K ∩Z h (0) n (α) -ϕ 2 -n α ≤ θ n , n ∈ N. (38
Ψ = Ψ g ∈ C p-d R, R d +1 satisfies Ψ = 0 ψ , ψ ∈ C p-d (R, R) . ( 39
)
Then H A is C p -convergent.

Proof:

The proof is adapted from the proofs in [START_REF] Dubuc | Hermite subdivision schemes and Taylor polynomials[END_REF][START_REF] Merrien | A generalized Taylor factorization for Hermite subdivisions schemes[END_REF]. Given f 0 ∈ ℓ d +1 (Z), let g 0 = T d f 0 . We define the following two sequences:

f n+1 = D -n-1 S A (D f n ) and g n+1 = S B g n , n ∈ N. Since T d S A = 2 -d S B T d , we can directly deduce that f n+1 = 2 nd T d D n f n .
With the convergence of f n (0), let y i := lim n→+∞ f (i ) n (0), i = 0, . . . , d . Then we define Φ recursively beginning with φ d = ψ and setting

φ i (x) = y i + 1 0 x φ i +1 (t x) d t i = d -1, . . . , 0. ( 40
) Then Φ = [φ i ] i =0,...d is continuous with φ (d -i ) i = ψ.
Fixing a compact K ⊂ R, we will prove by a backward finite recursion that for k = d , d -1, . . . , 0, there exists a sequence ε n with limit 0 such that

f (k) n (γ) -φ k 2 -n γ ≤ ε n , γ ∈ Z ∩ 2 n K . ( 41
)
The case k = d is an immediate consequence of the convergence of the last row of g n and

g (d ) n = f (d ) n , which yields for any γ ∈ Z ∩ 2 n K that f (d ) n (γ) -ψ(2 -n γ) ≤ ε n , (42)
while, for k < d , the convergence of the appropriate component of g n to zero implies that

2 n(d -k) ∆ f (k) n (γ) - 1 2 n f (k+1) n (γ) + d -k ℓ=2 t k,k+ℓ 1 2 nℓ f (k+ℓ) n (γ) ≤ ε n , (43)
for a sequence ε n that tends to zero for n → ∞.

To prove (41) for k = d -1, we define the sequences

h n = [ f (d -1) n , f (d ) n ] T . Then (43) be- comes 2 n ∆ f (d -1) n (•) -f (d ) n (•) ≤ ε n .
Because of (42), we can apply Lemma 30 and obtain that

f (d -1) n (γ) -φ d -1 2 -n γ ≤ θ n , γ ∈ 2 n K ∩ Z, which is (41) for k = d -1. To prove the recursive step k + 1 → k, 0 ≤ k < d -2, we get from (43) that, for γ ∈ Z ∩ 2 n K , 2 n ∆ f (k) n (γ) -f (k+1) n (γ) ≤ ε n 2 n(d -k) + d -k ℓ=2 |t k,k+ℓ | 2 nℓ f (k+ℓ) n (γ) (44)
Since (41) holds for j > k, it follows that

lim n→∞ f ( j ) n (γ) -φ j 2 -n γ = 0
uniformly for γ ∈ Z ∩ 2 n K and since φ j is bounded on K , so is the sequence f ( j ) n (γ) on Z ∩ 2 n K . Thus the right hand side of (44) converges to zero so that it immediately implies (41) using again Lemma 30.

As a consequence of Theorem 31 and Lemma 28 we also have the following results.

Corollary 32 Let A, B ∈ ℓ (d +1)×(d +1) (Z) be two masks related by the the factorization T d S A = 2 -d S B T d for some generalized complete Taylor operator Td . For any initial data f 0 ∈ ℓ d +1 (Z) and associated refinement sequence f n of the Hermite scheme H A , we suppose that the sequence f n (0) converges to a limit

y ∈ R d +1 . If S B is contractive and b * d d (1) = 1, then H A is C d -convergent.
Remark 33 The condition that f n (0) converges can be discarded by using the techniques from [START_REF] Conti | Convergence of level dependent Hermite subdivision schemes[END_REF]. The factorization arguments used there can easily be seen to carry over to the situation of arbitrary generalized Taylor operators. Nevertheless, we prefer the proof given here due to its analytic flavor which nicely corresponds to the graphs shown later. There the function ψ equals the last derivative of the limit function in accordance with the proof above.

Corollary 34 If, for a mask A ∈ ℓ (d +1)×(d +1) (Z), there exists a spectral chain V and the difference scheme defined by

T d S A = 2 -d S B T d is contractive and satisfies b * d d (1) = 1, then H A is C d -convergent.

Remark 35 A normalization property like b * d d (1) = 1 has to exist in order to describe convergence since all the other properties hold regardless of a rescaling of A and thus B by any constant. But of course such a rescaling either makes the iteration diverge or converge to zero for any input data which both is excluded from the notion of convergence of a subdivision scheme.

Chains seem to be the proper generalization of sum rules from scalar subdivision. They provide a large and exhaustive family of annihilators for factorization of subdivision operators; the only requirement a generalized Taylor operator has to fulfill is the -1 on the first superdiagonal that encodes, in a discrete way, the fact that the j + 1st entry of the limit function is the derivative of the j th entry. This leads us to the following conjecture.

Conjecture Given a mask A ∈ ℓ (d +1)×(d +1) (Z). The Hermite subdivision scheme H A is C d -convergent if and only if there exists a spectral chain V such that the difference scheme defined by

T d S A = 2 -d S B T d is contractive and satisfies b * d d (1) = 1.

Unfactoring constructions

In this section we consider the construction of convergent Hermite subdivision schemes that factorize with respect to a given generalized Taylor operator, thus showing that there exist whole classes of convergent Hermite subdivision schemes that do not satisfy the spectral condition. In particular, the spectral condition is not necessary for C d -convergence. These constructions will be based on determining a contractive difference scheme B . The difficulty, as in all vector subdivision schemes, lies in the fact that, in contrast to the scalar case, not every vector subdivision scheme is the difference scheme of a finitely supported vector or Hermite subdivision schemes, but that more intricate algebraic conditions have to be taken into account. Since the remainder of this section is rather technical, let us first point out the main, simple idea behind the construction. By the Taylor factorization property, the symbols of A and B are related by

T * d (z) A * (z) = B * (z) T * d (z 2 ), i.e., A * (z) = T * d (z) -1 B * (z) T * d (z 2 ). ( 45
)
Hence, the mask B with the contractive operator S B defines A * , but, due to occurrence of the inverse of the symbol of, this can be a rational function. In order to make it a Laurent polynomial, further algebraic conditions on the components of B * have to be satisfied. We will identify these conditions in the next section and then show how they can be easily satisfied for triangular, contractive choices of B .

Conditions on the difference schemes

We begin with an inversion of the Taylor operator.

Lemma 36 For any generalized complete Taylor operator T d , there exists an upper triangular matrix P * (z) of Laurent polynomials such that

T * d (z) -1 = 1 z -1 -1 D * d (z)P * (z) D * d (z) -1 , ( 46
)
where

D * d (z) =       1 z -1 -1 . . . (z -1 -1) d       .
Moreover p * j j (z) = 1, j = 0, . . . , d , and

P * (1) =    1 . . . 1 . . . . . . 1    . ( 47
)
Proof: Since

T * d (z) =        z -1 -1 * . . . * z -1 -1 . . . . . . . . . * z -1 -1        = (z -1 -1) I - N z -1 -1
with the strictly upper triangular nilpotent matrix

N =           0 1 * . . . * 0 1 . . . . . . 0 . . . * . . . 1 0           ∈ R (d +1)×(d +1) , N d +1 = 0, it follows that T * d (z) -1 = 1 z -1 -1 I + d j =1 N z -1 -1 j =         p * 00 (z) z -1 -1 p * 01 (z) (z -1 -1) 2 . . . p * 0d (z) (z -1 -1) d +1 p * 11 (z) z -1 -1 . . . . . . . . . p * d -1,d (z) (z -1 -1) 2 p * d d (z) z -1 -1         = 1 z -1 -1 D * d (z)P * (z) D * d (z) -1 .
The property of the diagonal elements p j j is immediate from the form of N , in particular

d j =1 N z -1 -1 j has a null diagonal.
For the computation on the off-diagonal elements, we notice that due to

N j =               0 . . .
              , it follows that p * j k (z) (z -1 -1) k-j +1 = 1 (z -1 -1) k-j +1 + q j k (z) (z -1 -1) k-j = (z -1 -1)q j k (z) + 1 (z -1 -1) k-j +1 ,
which gives (47).

Example 37 For the generalized complete Taylor operator T ∆,d from (21), we get the constant polynomial matrix

P * (z) = P * (1) =    1 . . . 1 . . . . . . 1    . Next, we compute C * (z) := T * d (z) -1 B * (z), by first noting that 1 z -1 -1 D * d (z) -1 B * (z) =      b * 00 (z) z -1 -1 . . . b * 0d (z) z -1 -1 . . . . . . . . . b * d 0 (z) (z -1 -1) d +1 . . . b * d d (z) (z -1 -1) d +1      .
Note that without further assumptions this can be a matrix of rational functions. Therefore the entries c * j k (z) of

C * (z) = T * d (z) -1 B * (z) = (z -1 -1) -1 D * d (z) P * (z) D * d (z) -1 B * (z)
satisfy, for j , k = 0, . . . , d ,

c * j k (z) = (z -1) j d ℓ= j p * j ℓ (z) b * ℓk (z) (z -1 -1) ℓ+1 = d ℓ= j p * j ℓ (z) b * ℓk (z) (z -1 -1) ℓ-j +1 .
Then, the components a * j k (z) of the final result

A * (z) = T d * (z) -1 B * (z) T d * (z 2 ) = C * (z) T d * (z 2 ) satisfy, since T d * (z 2 ) r k = 0 for r > k, a * j k (z) = d r =0 c * j r (z) T d * (z 2 ) r k = k r =0 c * j r (z) T d * (z 2 ) r k = (z -2 -1)c * j k (z) - k-1 r =0 c * j r (z) w k,r +1 = (z -1 + 1) d ℓ= j p * j ℓ (z) b * ℓk (z) (z -1 -1) ℓ-j - k-1 r =0 w k,r +1 d ℓ= j p * j ℓ (z) b * ℓr (z) (z -1 -1) ℓ-j +1 , hence, a * j k (z) = d ℓ= j p * j ℓ (z) (z -1 -1) ℓ-j (z -1 + 1) b * ℓk (z) - k-1 r =0 w k,r +1 b * ℓr (z) z -1 -1 , j , k = 0, . . . , d . ( 48
)
Now we can state a condition of B * that ensures that A * is indeed a Laurent polynomial.

Lemma 38 If for any j , k = 0, . . . , d , there exists a Laurent polynomial h * j k (z) such that

(z -1 + 1) b * j k (z) - k-1 r =0 w k,r +1 b * j r (z) z -1 -1 = (z -1 -1) j h * j k (z), ( 49
) then A ∈ ℓ (d +1)×(d +1) (Z).
Proof: Since p * j ℓ (1) = 1, all the terms of the outer sum in (48) are polynomials if and only if

(z -1 + 1) b * ℓk (z) - k-1 r =0 w k,r +1 b * ℓr (z) z -1 -1 , ℓ = j , . . . , d ,
has an (ℓj )-fold zero at 1 for all j ≤ ℓ, in particular for j = 0, which yields (49) after replacing ℓ by j .

The simplest way to solve (49) is to set

b * j k (z) = (z -1 -1) j h * j k (z), j = 0, . . . , d -1, k = 0, . . . , d , (50)
which we can even choose in a upper triangular way by setting h * j k = 0 for k > j . Note that this choice is even independent of the generalized Taylor operator.

For the final row, however, we cannot use this approach since it would yield b * d d (1) = 0, thus contradicting the requirement from Lemma 28. To overcome this problem, we set

b * d j (z) = (z -1 -1) g * d j (z) =: (z -1 -1) d -j h * d j (z -1 ), j = 0, . . . , d . (51)
We want to construct h * d j in such a way that for j = 0, . . . , d the polynomials

(z -1 + 1) b * d j (z) - j -1 k=0 w j ,k+1 b * d k (z) z -1 -1 = (z -1 + 1)(z -1 -1) d -j h * d j (z -1 ) - j -1 k=0 w j ,k+1 (z -1 -1) d -k-1 h * d k (z -1 ) = (z -1 -1) d -j (z -1 + 1)h * d j (z -1 ) - j -1 k=0 w j ,k+1 (z -1 -1) ( j -1)-k h * d k (z -1 ) = (z -1 -1) d -j (z -1 + 1)h * d j (z -1 ) - j -1 k=0 w j , j -k (z -1 -1) k h * d , j -1-k (z -1 )
have a zero of order d at 1. Since w j j = 1, this is equivalent, after replacing z by z -1 , to a zero of order j at 1 of the Laurent polynomials

q j (z) := (z + 1)h * d j (z) -h * d , j -1 (z) - j -1 k=1 w j , j -k (z -1) k h * d , j -1-k (z). (52)
This implies that 0 = q j (1) = 2h * d j (1) -h * d , j -1 (1), j = 1, . . . , d , which yields, together with the requirement that b

* d d (1) = 1, that h * d j (1) = 2 d -j , j = 0, . . . , d . (53)
The r th derivative, r = 1, . . . , j , of q j is

q (r ) j (z) = r s=0 r s d s d z s (z + 1) h * d j (r -s) (z) -h * d , j -1 (r ) (z)
-

j -1 k=1 w j , j -k r s=0 r s d s d z s (z -1) k h * d , j -1-k (r -s) (z) = (z + 1) h * d j (r ) (z) + r h * d j (r -1) (z) -h * d , j -1 (r ) (z) - j -1 k=1 w j , j -k min(k,r ) s=0 r s k! (k -s)! (z -1) k-s h * d , j -1-k (r -s) (z).
Therefore, we can express the additional requirements as 0 = q (r ) j (1)

= 2 h * d j (r ) (1) + r h * d j (r -1) (1) -h * d , j -1 (r ) (1)
-

r k=1 w j , j -k r ! (r -k)! h * d , j -1-k (r -k) (1), r = 1, . . . , j -1, (54)
and, with r = j ,

0 = 2 h * d j ( j ) (1) + r h * d j ( j -1) (1) -h * d , j -1 ( j ) (1)
-

j -1 k=1 w j , j -k j ! ( j -k)! h * d , j -1-k ( j -k) (1). (55)
Together, ( 54) and ( 55) can be used to build the polynomials h * d j recursively. This construction allows us to easily create factorizable schemes via (54) and ( 55), but it is more difficult to choose h * d 0 (z) in such a way that the final h * d d (z) is the symbol of a contractive scheme. To achieve this, we perform the recurrence in the opposite direction, which is still easy for T ∆ .

Example For the generalized Taylor operator T ∆,d we get the simplified conditions

0 = 2 h * d j (r ) (1) + r h * d j (r -1) (1) -h * d , j -1 (r ) (1), r = 1, . . . , j , (56) or h
* d j (r ) (1) = 1 2 h * d , j -1 (r )
(1) -r h * d j (r -1)

(1) , r = 1, . . . , j.

(57)

To come up with convergent schemes of arbitrary size that factor with T ∆,d , we now solve (56) for h * d , j -1 , replace j -1 by j and thus get

h * d j (r ) (1) = 2 h * d , j +1 (r )
(1)

+ r h * d , j +1 (r -1) (1)
, r = 1, . . . , j + 1, which leads to the explicit formula

h * d j (z) = 2 d -j + n+d -j r =1 2 h * d , j +1 (r )
(1)

+ r h * d , j +1 (r -1) (1)
r ! (z -1) r , j = d -1, . . . , 0, ( 58
)
initialized with a polynomial h * d d of degree n. Starting with the simplest choice h * d d (z) = 1 2 (z + 1), we thus get h * d ,d -1 (z) = 2 + 2(z -1) + 1 2 (z -1) 2 = 1 2 (z + 1) 2 h * d ,d -2 (z) = 4 + 6(z -1) + 3(z -1) 2 + 1 2 (z -1) 3 = 1 2 (z + 1) 3 .
If we now set f n (z) := 1 2 (z + 1) n , then f (r ) n (1) = n! (n-r )! 2 n-r -1 and the fact that

2 f (r ) n-1 (1) + r f (r -1) n-1 (1) = (n -1)! (n -1 -r )! 2 n-1-r + r (n -1)! (n -r )! 2 n-1-r = (n -1)! (n -1 -r )! 2 n-1-r 1 + r n -r = (n -1)! (n -1 -r )! 2 n-1-r n n -r = n! (n -r )! 2 n-r -1 = f (r ) n (1)
shows that indeed

h * d j (z) = 1 2 (z + 1) d -j +1 , j = 0, . . . , d , (59)
satisfy the recurrence (58) and therefore

b * d j (z) = (z -1 -1) d -j h * d j (z -1 ) = 1 2 z -1 + 1 z -2 -1 d -j
is a proper choice. For d = 2, for example, we can set

B * (z) =    -z-1 2 z 0 0 (z-1) 2 z 2 (z-1) 2 4 z 2 0 (z-1) 2 (1+z) 3 2 z 5 -(z-1) (1+z) 2 2 z 3 1+z 2 z   
and get the corresponding 4 2 z 6 0 0

A * (z) = 1/4     - (1+z) (-1-3z-6z 2 +2 z 3 ) 2 z 4 -7 z 2 -1 4 z 2 -1 4 (z-1) (1+z) (-1-3z-5z 2 +z 3 ) 2 z 5 (z-1) (5z 2 -1) 4 z 3 z-1 4 z (z-1) 2 (1+z)
   
which yields a C 2 -convergent subdivision scheme that does not satisfy the classical spectral condition [START_REF] Dubuc | Hermite subdivision schemes and Taylor polynomials[END_REF]. It satisfies, however, a spectral chain condition related to the Taylor operator T ∆,d . The result is shown in Fig. 1.

For some time it was conjectured that all C d -convergent Hermite subdivision schemes must satisfy a spectral condition. This is disproved by the following example of a family of convergent schemes that satisfies no spectral condition.

Theorem 40 If the nonzero elements of the matrix B * are of the form b

* j k (z) = (z -1 -1) j +1 h * j k (z), 0 ≤ k < j < d , b * j j (z) = (z -1 -1) j +1 2 j +1 , j = 0, . . . , d -1, b * d j (z) = 1 2 (z -1 + 1) z -2 -1 d -j j = 0, . . . , d ,
then there exists a C d -convergent Hermite subdivision scheme whose mask

A satisfies T ∆ S A = 2 -d S B T ∆ .
Proof: Since B is lower triangular with contractions on the diagonal, the scheme S B is contractive. The factorization is satisfied by construction. f (2) Figure 1: Limit functions for Example 39, showing the three entries of the limit function of the Hermite subdivision scheme and the limit function of the associated convergent difference scheme.

A generic construction for arbitrary Taylor operators

For an arbitrary generalized Taylor operator T , we want to construct convergent schemes that factorize with respect to T , thus showing that convergence theory widely exceeds spectral conditions.

Theorem 41 For any d ∈ N and any generalized Taylor operator T of order d there exists a convergent Hermite subdivision scheme with mask A that factors with T , that is, such that T S A = 2 -d S B T for some appropriate B .

The proof continues the construction from the preceding subsection by giving an explicit way to construct the polynomials h * d j , j = 0, . . . , d , in such a way that S A admits the factorization. Proof: We will again set b

* d j (z) = (z -1 -1) d -j h * d j (z -1 ), (60)
and make use of ( 56) and (57) to determine the vectors

h j =    h j , j +1 . . . h j 1    :=      h * d j ( j +1) (1) . . . h * d j ′ (1)      ∈ R j +1 , j = 0, . . . , d -1,
which define B * and eventually the desired mask A * . We stack these vectors into the column vector

h :=    h d -1 . . . h 0    ∈ R d (d +1) 2 .
Again, let h * d d (z) be the symbol of a contractive mask and recall that

h * d j (1) = 2 d -j , j = 0, . . . , d , (61)
is necessary due to Lemma 28 to obtain S B as a convergent vector subdivision scheme. Taking (61) into account, the requirement for h d -1 can be obtained by setting j = d in (54), which yields

h d -1,r + r -1 k=1 w d ,d -k r ! (r -k)! h d -1-k,r -k = 2 h * d d (r ) (1) + r h * d d (r -1) (1) -w d ,d -r 2 r +1 , r = 1, . . . , d -1.
In the same way, (55) transforms into

h d -1,d + d -1 k=1 w d ,d -k d ! (d -k)! h d -1-k,d -k = 2 h * d d (d ) (1) + d h * d d (d -1) (1).
In matrix form, this can be rewritten as

b d =        1
H d ,k = -w d ,k+1            d ! (k+1)! . . . (d -k)! 1! 0 . . . 0 . . . . . . . . . 0 . . . 0            ∈ R d ×k+1 , k = 0, . . . , d -2,
and

b d :=        2 h * d d (d ) (1) + d h * d d (d -1) (1) 2 h * d d (d -1) (1) + (d -1) h * d d (d -2) (1) -2 d w d ,1 . . . 2 h * d d (1) (1) + 1 -4 w d ,d -1        ∈ R d .
The conditions (54) and (55) for q d -1 can, in the same way, be written as

0 = 2h d -1,d -1 + (d -1)h d -1,d -2 -h d -2,d -1 - d -2 k=1 w d -1,k (d -1)! k! h k-1,k ,
as well as for r = 2, . . . , d -2,

2 r +2 w d -1,d -1-r = 2h d -1,r + r h d -1,r -1 -h d -2,r - r -1 k=1 w d -1,d -1-k r ! (r -k)! h d -2-k,r -k ,
and finally the case r = 1

2 d -1 = 2h d -1,r -h d -2,r .
taking the matrix form

b d -1 =        0 2 d -1 -1 . . . * 0 2 . . . -1 0 . . . . . . 2 . . . . . . 0 2 -1 . . . 0        a (63) =: C d -1 -I d H d -1,d -3 . . . H d -1,0 h with C j :=        0 2 j 0 2 . . . . . . . . . 2 0 2        ∈ R j × j +1 , j = 2, . . . , d -1, C 1 := 0 2 ,
and

H d -1,k = -w d -1,k+1            (d -1)! (k+1)! . . . (d -1-k)! 1! 0 . . . 0 . . . . . . . . . 0 . . . 0            ∈ R d -1×k+1 , k = 0, . . . , d -3.
With the general definition

H j ,k = -w j ,k+1             j ! (k+1)! . . . ( j -k)! 1! 0 . . . 0 . . . . . . . . . 0 . . . 0             ∈ R j ×k+1 , k = 0, . . . , j -2, j = 1, . . . , d , (64)
the conditions (54) and (55) result in the system

b =    b d . . . b 1    =         I d -H d ,d -2 -H d ,d -3 . . . -H d ,0 C d -1 -I d H d -1,d -3 . . . H d -1,0 . . . . . . . . . . . . C 2 -I 2 H 2,0 C 1 -1         h =: H h, (65)
noting that 1 = I 1 = H

B * (z) =          z -1 -1 2 (z -1 -1) 2 h * 10 (z) (z -1 -1) 2 4 . . . . . . . . . (z -1 -1) d h * d -1,0 (z) . . . (z -1 -1) d h * d -1,d -2 (z) (z -1 -1) d 2 d b * d 0 (z) . . . b * d ,d -2 (z) b * d ,d -1 (z) b * d d (z)         
is the symbol of a contractive scheme that satisfies the conditions from Lemma 28 and for which there exists a mask A such that S A = S B T . Therefore, A defines a C d -convergent Hermite subdivision scheme.

Remark 42 Recall that the whole construction process only had the purpose of finding the last row of the lower triangular symbol B * (z). All other entries could be chosen in a straightforward way.

Lemma 43 Matrix H from (65) satisfies | det H | = 1.

Proof: Since the first column of C d -1 is zero, we can start with an expansion with respect to the first column, yielding that det H is the same as the determinant of A with first row and column erased. Then, we note that the last row of the matrix in (62) has only one nonzero entry, namely -1. Expansion with respect to this row also removes the column that contains the 2 in the last row of (65). Expanding with respect to this row then removes the row that contains the last nonzero element in H d ,d -2 in (62), so that we can now expand with respect to the second last row of (62). Circling in this way, we expand the determinant by means of factors that are ±1, hence, the determinant of H is ±1 and in particular independent of T , that is, independent of w 1 , . . . , w d .

Examples

To illustrate the potential of the methods, we start with two examples of masks obtained by the construction process in Theorem 41. We restrict ourselves to the simplest nontrivial case d = 2 here.

Example 44 One parameter, w 21 , can be chosen freely. The associated linear system for h in (65) has the simple form

H = I 2 -H 2,0 C 1 -1 =   1 0 2w 21 0 1 0 0 2 -1   , H 2,0 = -w 21 2 0 which explicitly becomes   1 2w 21 1 2 -1     h 12 h 11 h 01   =    2 h * d d ′′ (1) + 2 h * d d ′ (1) 2 h * d d ′ (1) + 1 -4w 21 2    and gives h 11 = 2 h * d d ′ (1) + 1 -4w 21 h 01 = 2a 11 -2 = 4 h * d d ′ (1) -8w 21 h 12 = 2 h * d d ′′ (1) + 2 h * d d ′ (1) -2w 21 a 01 = 2 h * d d ′′ (1) + h * d d ′ (1) (1 -4w 21 ) + 8w 2 21 .
Using the simplest possible choice h

h * 20 (z) = 4 + (2 -8w 21 )(z -1) = 2 ((1 -4w 21 )z + (1 + 4w 21 )) , yielding b * 22 (z) = 1 2 (z -1 + 1) b * 21 (z) = (1 -4w 21 + 8w 2 21 )z -3 + 8w 21 (1 -3w 21 )z -2 -(1 + 4w 21 -24w 2 21 )z -1 -8w 2 21 b * 20 (z) = (4 -8w 21 )z -2 -(4 -16w 21 )z -1 + 8w 2 21 .
The resulting limit functions are plotted in Fig 2.

Example 45 In continuation of Example 44, we now choose an arbitrary contractive version based on h

* d d (z) = (z + 1) n 2 n -1 0 1 2 -50 0 50 ψ -1 0 1 2 -2 -1 0 1 2 3 f (0) -1 0 1 2 -5 0 5 f (1) -1 0 1 2 -50 0 50 f (2)

which has the property that h

* d d (1) = 1, h * d d ′ (1) = n 2 , h * d d ′′ (1) = n(n -1) 4 , so that h 12 = 2 n(n -1) 4 + n 2 (1 -4 w 21 ) + 8w 2 21 = n(n + 1) 2 -4nw 21 + 16w 2 21 , h 11 = n + 1 -4w 21 h 01 = 2n -8w 21 ,
which leads to the graphs shown in Fig. 3. This even gives a whole family of convergent schemes with the additional parameter n.

The last example revisits a Hermite subdivision scheme based on B-splines that was introduced in [START_REF] Merrien | A generalized Taylor factorization for Hermite subdivisions schemes[END_REF] and further studied in [START_REF] Merrien | Extended Hermite subdivision schemes[END_REF] as one of the first examples of a family of convergent Hermite subdivision schemes that do not satisfy the spectral condition. This scheme is based on a construction detailed by Micchelli in [START_REF] Micchelli | Mathematical Aspects of Geometric Modeling[END_REF]. Let ϕ 0 (x) = χ [0,1] and define, for r = 1, 2, . . ., the cardinal B-spline ϕ r = ϕ 0 * ϕ r -1 . We recall that ϕ r is a C r -1 piecewise polynomial of degree r with support [0, r +1] that satisfies the refinement equation

ϕ r (x) = 1 2 r α∈Z r + 1 α ϕ r (2x -α), i j = i ! j !(i -j )! if 0 ≤ j ≤ i , 0
otherwise.

The function v(x) = α∈Z f (0) 0 (α)ϕ r (xα) can be written as v(x) = α∈Z f (0) n (α)ϕ r (2 n x -α), n ∈ N 0 , where

f (0) n+1 (•) = β∈Z a r (• -2β) f (0) n (β), a r (α) = 1 2 r r + 1 α , α ∈ Z. (66)
We have proved in [START_REF] Merrien | Extended Hermite subdivision schemes[END_REF]Proposition 5.3] that for i = 0, . . . , r one has .

has as limit function the vector consisting of the B-spline and its derivatives but does not satisfy the classical spectral condition, see [START_REF] Merrien | A generalized Taylor factorization for Hermite subdivisions schemes[END_REF].

Remark 47 The scheme of Example 46 was studied in [START_REF] Merrien | A generalized Taylor factorization for Hermite subdivisions schemes[END_REF] by means of similarity transforms of the masks which was sufficient to show its convergence. The approach presented here is different and more systematic.

In the following, we prove that the Hermite scheme from Example 46 possesses a spectral chain. where the d -j -th last components of v p are zero if p ∈ Π j , j < d . Secondly, (67) yields S a r p j = 2 -j p j and the first component of v p j is p j , since the only non zero column of the matrices A(α) is the first one, we therefore deduce that S A v p j = S A p j * = S A v p j = 1 2 j v p j , j = 0, . . . , d , so that for j = 0, . . . , d , the vectors v j = v p j satisfy the spectral condition. To show that the associated v j form a chain, we have to find the appropriate generalized Taylor operator annihilating v d , its uniqueness being guaranteed by Corollary 8. This operator is T S,d from ( 22 -(z-1) 3 z (1+z) 4 2 (z-1) 2 z 3 (1+z) 3 2

-(z-1) z 3 (1+z) 2 2 z 3 (1+z) 2
-(z-1) 3 z (1+z) 4 2 (z-1) 2 z 3 (1+z) 3 2

-(z-1) z 3 (1+z) 2 2 z 3 (1+z) 2
-(z-1) 3 z (1+z) 4 2 (z-1) 2 z 3 (1+z) 3 2

-(z-1) z 3 (1+z) 2 2 z 3 (1+z) 2       
.

We close the paper with a simple identity on forward and backward differences needed for Example 48 that may, however, be of independent interest.

n j + 1 = n-1 k= j k j , 0 ≤ j ≤ n -1, (69)
which is easily proved by induction on n: calling the left hand side of (69) f (n) and the right hand side g (n), the initial step f ( j + 1) = g ( j + 1) = 1 is obvious, while

f (n + 1) -f (n) = n + 1 j + 1 - n j + 1 = n j = g (n + 1) -g (n)
advances the induction.

C d function according to Definition 2 if 1 .

 1 there exists a scheme S B such that T C ,d S A = 2 -d S B T C ,d and S B is a convergent vector subdivision scheme with limit function ψ g = e d f g , for given input data g , where e d = [0, . . . , 0, 1] T and f g is a scalar valued function, 2. there exists a scheme S B such that T C ,d S A = 2 -d S B T C ,d and S B is contractive.

21 ( 1 ) 1 ) = 2 .

 112 = 0, otherwise (z -1 -1) -1 B * 21 (z) has a pole at 1. Second, the condition S B e d = e d is equivalent to B * (-1)e d = 0 and B * (1)e d = 2e d . The first one of these requirements is automatically satisfied according to (34), the second one becomes 2B * 22 (Remark 29 Not that B * 22 from (33) is just the scalar valued Laurent polynomial b * d d . Now we study the convergence of the Hermite scheme whenever we have one of the factorizations: T S A = 2 -d S B T or T S A = 2 -d S B T . To that end, we first recall the one dimensional case of [15, Lemma 3].

)

  Theorem 31 Let A, B ∈ ℓ (d +1)×(d +1) (Z) be two masks related by the the factorization T d S A = 2 -d S B T d for some generalized incomplete Taylor operator T d .

Figure 2 :

 2 Figure 2: Limit functions for the constructions of Example 44 for the values w 21 = 1 2 (blue, solid) and w 21 = 1 (red, dashed).

Figure 3 :

 3 Figure 3: Limit functions for Example 45 for the values w 21 = 1 2 (blue, solid) and w 21 = 1 (red, dashed) and n = 5.

S a r p i = 1 2

 1 i p i , p i := ℓ (r -i ) (x) = α∈Z 2 ni ∆ i f (0) n (α -i ) ϕ r -i 2 n x -α , i = 0, . . . , r -1,we define Hermite subdivision schemes of degree d ≤ r with mask A(α) and support [0, r + d + 1] by applying differences to the mask a r , yielding the following observation.Example 46The Hermite subdivision scheme based on ∆a r (α -1) 0 . . . 0 ∆ 2 a r (α -2) 0 . . . 0 . . . ∆ d a r (α -d ) 0 . . . 0

∈

  Firstly, the computation of Taylor expansions yields that there for p ∈ Π d the vectorsv p = [p, p ′ , . . . , p (d ) ] T and v p = [p, ∆p(• -1), . . . , ∆ d p(• -d )] T satisfy v p = R v p , R (d +1)×(d +1) ,

) in Example 16 .

 16 Indeed, by Lemma 49 proved at the end of this section,T S,d v d d -j = ∆ ∆ j p d (• -j ) -d -j k=1 ∆ k ∆ j p d (• -j ) (• -k) = ∆ d p d (• -j -d + 1) -∆ d p d (• -j -d ) = 0, j = 0, . . . ,d , since ∆ d p d = 1. The same argument also shows that T S,d v j = 0, j = 0, . . . , d -1. Therefore V forms a spectral chain for S A and by Theorem 25 there exists a finite mask B ∈ ℓ (d +1)×(d +1) (Z) such that T S,d S A = S B T S,d . Example 48 (Example 46 continued) For r = 4, d = 3, we obtain B * (z)

Lemma 49 1 k=1∆

 491 For p ∈ Π and n ∈ N we have that∆p = nk p(• -k) + ∆ n p(• -n + 1). (68)Proof: Expanding the differences as∆ k p(• -k) = claimfollows by taking into account the combinatorial identity

  Let v := [v d , . . . , v 0 ] T be a vector of polynomials in Π d +1 with v 0 = 1. Then v ∈ V d if and only if there exists a generalized complete Taylor operator T d such that T d v = 0.

	Remark 6 The Taylor operator becomes generalized for d ≥ 2, otherwise we simply recover the
	classical case, see Example 16.
	Lemma 7
	 ∆ -1 1 * . . . * . . . . . . . . . . . . . . . . . . *        	= ∆I + t j k j ,k=0,...,d .	(13)
	∆