Stavros Papadopoulos
email: s.papadopoulos11@imperial.ac.uk

Konstantinos Votis
email: kvotis@iti.gr

Christos Alexakos
email: alexakos@ceid.upatras.gr

Dimitrios Tzovaras
email: tzovaras@iti.gr

Feature extraction and visual feature fusion for the detection of concurrent prefix hijacks

This paper presents a method for visualizing and analyzing Multiple Origin Autonomous System (MOAS) incidents on Border Gateway Protocol (BGP), for the purpose of detecting concurrent prefix hijack. Concurrent prefix hijacks happen when an unauthorized network originates prefixes that belong to multiple other networks. Towards the goal of accurately identifying such events, multiple features are extracted from the BGP records and visualized using parallel coordinates enhanced with visual querying capabilities. The proposed visual queries enable the analyst to select a significant subset of the initial dataset for further analysis, based on the values of multiple features. This procedure allows for the efficient visual fusion of the proposed features and the accurate identification of prefix hijacks. Most of the previous approaches on BGP hijack detection depend on static methods in order to fuse the information from multiple features and identify anomalies. The proposed visual feature fusion, however, allows the human operator to incorporate his expert knowledge into the analysis, so as to dynamically investigate the observed events, and accurately identify anomalies. The efficiency of the proposed approach is demonstrated on state-of-the-art BGP events.

Introduction

Multiple Origin Autonomous System (MOAS) [START_REF] Zhao | An Analysis of BGP Multiple Origin AS (MOAS) Conflicts[END_REF] conflicts occur when a particular prefix appears to originate from more than one AS (Autonomous System). Although MOAS incidents occur often for legitimate reasons (e.g. multi-homing, This work has been partially supported by the European Commission through the project FP7-ICT-317888-NEMESYS funded by the 7th framework program. The opinions expressed in this paper are those of the authors and do not necessarily reflect the views of the European Commission.

exchange point addresses etc [START_REF] Zhao | An Analysis of BGP Multiple Origin AS (MOAS) Conflicts[END_REF]), they might also be the result of a fault or an attack, where a Border Gateway Protocol (BGP) router falsely originates prefixes belonging to other organizations. The detection of such faults and attacks has been the main focus of the research community in the last years. In this paper, the main focus is the detection of concurrent prefix hijacks, in which an unauthorized network originates prefixes that belong to multiple other networks, usually due to router misconfigurations.

The proposed methods for prefix hijack identification are separated into two categories: authentication and detection. Authentication schemes [START_REF] Zheng | A light-weight distributed scheme for detecting ip prefix hijacks in real-time[END_REF][3] depend on the a priori knowledge of the prefix owners, while detection schemes make no such assumption but instead analyze the routing behavior in order to identify suspicious events. The approach presented in this paper falls into the second category.

The detection schemes depend on some type of feature extraction and feature fusion in order to detect BGP prefix hijacks. Although there are many well known techniques for algorithmic fusion [START_REF] Chowdhury | A Survey of Decision Fusion and Feature Fusion Strategies for Pattern Classification[END_REF], the result of such approaches is static and it does not capture the dynamic nature of the modern multivariate systems and the corresponding alterations of the features' cross-correlations. For this reason, visualization techniques can be utilized for the purpose of performing the feature fusion, and allow the user to incorporate his experience and knowledge into the analysis.

In this respect, this paper introduces a novel visual feature fusion method for the combination of different BGP features, extracted from the observed MOAS incidents. The ultimate goal of the proposed approach is the detection of concurrent prefix hijacks, in which an unauthorized network originates prefixes that belong to multiple other networks. In order to achieve this, visual queries are applied on the parallel coordinates visualization in order to enable the analyst to focus on a significant subset of the data for further analysis, based on the values of multiple features.

It should be noted that the BGP exhibits continuous alterations, with over 20,000 BGP messages exchanged every 5 minutes (in 2014). All these messages are analyzed using the proposed approach in order to firstly identify MOAS incidents, and afterwards extract meaningful features that will enable the anomaly detection procedure. The proposed approach has been applied on data collected for over 3 months with out any problems. But in this paper and without loss of generality, the demonstration is carried out with respect to data corresponding to a time period of 5 days.

The rest of the paper is organized as follows: Section 2 presents the related work. Section 3 presents the feature extraction methodology, while the proposed visual feature fusion method is detailed in section 4. Use case analysis takes place in section 5. Finally, the paper concludes in section 6.

Related work

The internet uses BGP as the defacto protocol for the exchange of routing information between Autonomous Systems (AS). An AS represents a collection of Internet Protocol prefixes under the control of one network operator. The distributed nature of BGP and the lack of security mechanisms, render it vulnerable to various types of attacks, as for example prefix hijacking or Man-In-the-Middle attacks [START_REF] Ballani | A study of prefix hijacking and interception in the internet[END_REF]. Towards this end, the research community has focused its efforts on the development of methods that could enable the detection of such anomalies in the BGP infrastructure.

Specifically, Deshpande et al. [START_REF] Deshpande | An online mechanism for BGP instability detection and analysis[END_REF] introduced multiple features that represent various aspects of the BGP update messages. A Generalized Likelihood Ratio (GLR) based hypothesis test is utilized onto each feature in order to detect time periods of instabilities. Majority voting is afterwards utilized in order to correlate the detected instabilities, and generate alerts for which more than half of the features indicate an anomaly. Unlike the proposed visual feature fusion method, the disadvantage of this approach is that the analyst is not able to change the parameters of the anomaly detection algorithm in order to get better detection rates.

Li et al. [START_REF] Li | An Internet routing forensics framework for discovering rules of abnormal BGP events[END_REF] propose the use of a signature based classifier, that is trained to recognize certain types of behaviors specific to BGP anomalies. The classifier is comprised of a collection of IF-THEN threshold based rules, which are applied onto multiple BGP features, extracted in different time windows. As with the aforementioned approach the anomaly results are also static, as the analyst is left out of the detection procedure.

Al-Rousan et al. [START_REF] Al-Rousan | Feature selection for classification of BGP anomalies using Bayesian models[END_REF] introduce multiple features that characterize the BGP activity. Feature selection methods are applied onto this set of features in order to select a specific subset that better characterizes BGP anomalies. Afterwards, Naive Bayes classifiers are used for the detection of BGP anomalies, including worm attacks and router misconfigurations. In comparison with the proposed approach the user is not able to change the parameters of the classification in order to find alternative or better results.

Zhang et al. [START_REF] Zhang | On detection of anomalous routing dynamics in BGP[END_REF] propose the use of signature and a statistical based methods for detecting anomalies in BGP. The signature based methods are comprised of a standard set of patterns in the BGP update messages, which are specific to BGP anomalies. The statistical based methods are applied onto multiple BGP features, in order to acquire an anomaly score for each one of them. A linear weighted sum of the scores of each feature is afterwards utilized, so as to fuse the features and acquire a single anomaly score. This procedure is repeated for each time window under investigation, in order to detect time periods of instability. The results of this work were utilized by Teoh et al. [START_REF] Teoh | Combining visual and automated data mining for near-real-time anomaly detection and analysis in BGP[END_REF], and combined with visualization methods. Specifically, the anomaly scores of each feature, as well as the global anomaly score are visualized along the BGP update messages selected by the analyst. Using the feedback provided by the visualization, the analyst is able to adjust the parameters of the statistical and signature based methods and increase the detection accuracy. The adjustable parameters, however, do not refer to the feature fusion procedure but rather to the definitions of anomalous BGP events and the threshold of the fused anomaly metric. The approach of including the analyst into the analytical procedure is related to the present work, which also incorporates visual methods to aid the analysis procedure. But unlike [START_REF] Teoh | Combining visual and automated data mining for near-real-time anomaly detection and analysis in BGP[END_REF], the present work utilizes the visualization to aid the visual feature fusion procedure.

MOAS Feature Extraction

This section presents the feature extraction methodology proposed in the context of this paper. The extracted features are able to quantify the degree of anomaly of each MOAS incident, while their fusion provides and complete view of the MOAS characteristics and enables the detection of concurrent prefix hijacks.

There are four features that are extracted from the MOAS events that occurred over a specific time period: 1)Country MOAS Probability, 2)AS Relationship, 3)Ownership duration, and 4)MOAS duration. Each one of them is described in detail in the paragraphs that follow.

The first feature is Country MOAS Probability, which represents the probability of occurrence of a MOAS event from the country of the new owner AS to the country of the old owner AS. This country based aggregation and analysis of the BGP activity, has been shown to capture the underlying geo-spatial coherence of the Internet routing information [START_REF] Theodoridis | A Novel Unsupervised Method for Securing BGP Against Routing Hijacks[END_REF]. Although the probability of occurrence of a MOAS event between two ASes can be used directly for anomaly detection, the country aggregation takes into account all the MOAS events between the two countries, and thus holds additional semantic information regarding the geospatial distribution of the MOAS incidents. This fact leads to a more accurate identification of concurrent prefix hijacks, since most of them target countries that are usually not targeted in normal behavior.

The AS Relationship between the two ASes involved in the MOAS incident has been used as a heuristic for reducing the number of false positives in prefix hijack detection [START_REF] Khare | Concurrent prefix hijacks: Occurrence and impacts[END_REF]. Under this consideration, it is also utilized in this context for the generation of a binary feature. This feature captures the AS pairs that have commercial relationships, and thus might use prefixes from the same set. The AS relationships where defined by Gao [START_REF] Gao | On inferring autonomous system relationships in the Internet[END_REF] and are comprised of Provider-To-Customer, Peer-To-Peer, and Sibling-To-Sibling relationships. If any type of relationship exists between two ASes, the AS Relationship feature has value 1, else it has value 0.

The Ownership duration feature captures the duration in hours that the new owner has been announcing the prefix involved in the MOAS incident. Since the new owner AS involved in the concurrent prefix hijacks is not the legitimate owner of the prefix, it is highly unlikely that it has been announcing the prefix for a long period. Thus, this feature captures this behavior and provides additional information for the accurate identification of concurrent prefix hijacks. It should be noted that absolute thresholds for anomaly detection using the aforementioned feature have been used in the literature [START_REF] Khare | Concurrent prefix hijacks: Occurrence and impacts[END_REF], but in the proposed approach combines the actual value of this feature with multiple other features, and allows the analyst to select appropriate thresholds dynamically, using visual queries.

The MOAS duration feature captures the duration in which each MOAS event is active. In the case of concurrent prefix hijacks, the MOAS incidents are highly unlikely to last for a long period. After the misconfiguration has been fixed, the prefixes return to their original owners. Although the MOAS duration can be a useful heuristic to distinguish between valid MOAS conflicts and invalid ones [START_REF] Zhao | An Analysis of BGP Multiple Origin AS (MOAS) Conflicts[END_REF], such differentiation on this feature alone can not be accurate enough to be a solution prefix hijack identification. In this context, the visual feature fusion procedure proposed in the context of this paper combines the values of this feature with multiple other features, in order to provide a holistic view of the MOAS activity to the analyst.

In addition to the aforementioned features that characterize the degree of anomaly of each MOAS incident, the MOAS events are also characterized by metadata. These metadata provide additional semantic information about each event and are used for root cause analysis by the visualization. These metadata include the following:Attacking AS, i.e. the AS number of the new owner of the prefix, Victim AS, i.e. the AS number of the old owner of the prefix, and Time, i.e. the exact date and time that the MOAS event occurred.

An overview of the extracted features and the metadata that are utilized for visual feature fusion and prefix hijack detection is presented in Table 1.

Visual feature fusion using Parallel coordinates and visual queries

The proposed visual feature fusion scheme is detailed in this section. Specifically, the features and metadata describing each MOAS event, which were presented in section 3, are visualized using parallel coordinates. The parallel coordinates are enhanced with filtering capabilities in order to enable the analyst to detect significant MOAS incidents that might contain anomalies. Specifically, bar sliders are attached onto each parallel coordinate that specify the allowed upper and lower bounds of each feature. These bar sliders can change size and position and are directly manipulated by the user of the visualization. This procedure allows the analyst to dynamically change the bounds of the features and as a result the MOAS events that are visualized. The direct feedback provided by the visualization with regards to the selection of MOAS events, enables the analyst to redefine the bounds, and find the best parameters in each case, according to the underling information.

Thus, for each feature and metadata f i the bounds are defined as

B i = {f low i , f upper i }.
Each MOAS event is characterized by its value in all the features and metadata. Furthermore, the following function is defined:

g(e j ) = true, if f low i ≤ f i (e j ) ≤ f high i , ∀i f alse, else (1)
where f i (e j ) is the value of the j th event e j in the i th feature f i . If g(e j ) is true then the MOAS event e j is visualized, while in the case that is false it is not. This interactive procedure enables for the visual fusion of the values of multiple features, in order to focus on suspicious MOAS incidents and lead to the accurate identification of concurrent prefix hijacks.

Discovery and analysis of prefix hijacks

This section demonstrates the use of the proposed feature extraction and visual feature fusion approach for the identification of concurrent prefix hijacks.

The BGP data were collected and analyzed from the RIPE routing monitoring service [START_REF]Routing Information Service project (RIS)[END_REF]. Specifically, the monitoring point of AS-3333 was utilized for the collection of the routing updates, and the analysis of the observed MOAS incidents.

It should be underlined that the monitoring period is larger than the period used for the visualization. The reason for this is that the values of the features are relevant to the total monitoring period, and small monitoring periods might not be enough for their accurate calculation. In both use cases examined in this section, the visualization period is set to one day, while the monitoring period is set to five days, two days before and two days after the visualization period.

The first use case involves a concurrent prefix hijack that occurred on 08-April-2010, around 16:00 GMT. In this incident, AS-23724 announced multiple prefixes it did not own, belonging to multiple other ASes [START_REF] Khare | Concurrent prefix hijacks: Occurrence and impacts[END_REF]. The monitoring period is set from 06-April-2010 to 10-April-2010, while the visualization period is set to 08-April-2010. The result of the visual feature fusion is depicted in figure 2. The values of the AS Relationship, Country MOAS Probability, Ownership duration, and MOAS duration are set to be: 0 (no relationship exists), smaller than 6%, smaller than 2 hours, and smaller than 24 hours, respectively. After the application of these visual queries, there is a small set of MOAS incidents that remains. It is apparent that in the first parallel coordinate, which represents the Attacking AS metadata, that AS-23724 is involved in multiple suspicious MOAS incidents, which last for a short period and have low probability of appearance. Furthermore, all these MOAS events are occurring almost simultaneously, around 16:00 GMT.

It should be noted that after the filtering procedure has taken place, there are two more MOAS incidents that remain. These incidents are not concurrent, since they do not concern multiple ASes. These events are short lived in the monitoring period and also have low probability of appearance. But due to the nature of BGP and the lack of ground truth, the answer to the legitimacy of Fig. 2. Visual feature fusion for the detection of a router misconfiguration event which tool place on 08-April-2010 [START_REF] Khare | Concurrent prefix hijacks: Occurrence and impacts[END_REF]. The AS Relationship feature is set to 0 (no relationship exists), the Country MOAS Probability is set to be smaller than 6%, the Ownership duration feature is set to be smaller than 2 hours, and the MOAS duration feature is set to be smaller than 24 hours. After this filtering, AS-23724 is still involved in multiple MOAS events, occurring simultaneously (at around 16:00 GMT) these events is difficult and out of the scope of this paper, which focuses on the detection of concurrent prefix hijacks.

The second use case concerns a concurrent prefix hijack that occurred on 28-April-2008 by AS-44237 [START_REF] Khare | Concurrent prefix hijacks: Occurrence and impacts[END_REF]. The monitoring period is set from 26-April-2008 to 30-April-2008, while the visualization period is set to 28-April-2008. The result of the visual fusion is depicted in figure 3. The bounds of the features are set using visual queries to: Country MOAS Probability smaller than 6%, Ownership duration smaller than 10 hours, and MOAS duration feature smaller than 24 hours. It is apparent in this figure that AS-44237 is involved in four suspicious MOAS events, which are visible from the monitoring point of AS-3333. All these MOAS incidents occurred on 28-April-2008 around 9:49 GMT.

Conclusions

The present paper proposed a method for visualizing and exploring BGP MOAS incidents, in order to detect concurrent prefix hijacks. Multiple features are extracted from the detected MOAS incidents, which quantify their degree of anomaly. An important aspect of the proposed features is the fact that they Fig. 3. Visual feature fusion for the detection of a router misconfiguration event which tool place on 28-April-2008 [START_REF] Khare | Concurrent prefix hijacks: Occurrence and impacts[END_REF]. The Country MOAS Probability is set to be smaller than 6%, the Ownership duration feature is set to be smaller than 10 hours, and the MOAS duration feature is set to be smaller than 24 hours. AS-44237 is involved in four suspicious MOAS events visible from the monitoring point of AS-3333.

present complex cross-correlations, and they have to be combined within the context of each other, as well as within the context of the other MOAS events. Towards this goal, this paper proposed the use of visual feature fusion of the aforementioned features, in order to allow for the accurate identification of concurrent prefix hijacks. To achieve this, a parallel coordinates view is proposed, which is further enhanced with filtering capabilities so as to discriminate between abnormal and normal events. This procedure allows the analyst to incorporate his/her expert knowledge and steer the analysis dynamically, so as to effetely detect prefix hijacks. The proposed was applied into a real-world BGP events, in order demonstrate its analytical potential.

It should be noted, that the proposed approach is general and can be applied in any set of relevant BGP features. Furthermore, it is also scalable, which renders it able to visualize and fuse a relatively large number of features by utilizing the power of parallel coordinates.

Fig. 1 .

 1 Fig. 1. The application of visual queries on the parallel coordinates utilized for visual feature fusion and the selection of significant data subsets.

Table 1 .

 1 Overview of the MOAS features and metadata used for the identification of concurrent prefix hijacks

	Description


Katerina Kalou
email: kaloukat@hpclab.ceid.upatras.gr

Dimitrios Koutsomitropoulos

Dimitrios Koutsomitropoulos Hpclab

Linking Data in the Insurance Sector: A Case Study

Keywords: insurance, property, casualty, OMG, ontology, linked data, big data

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

Introduction

An enterprise data model (EDM) captures the semantics of an organization for the purpose of communicating with the business community therefore, it can be considered a kind of ontology [START_REF] Hay | Data Modeling, RDF, & OWL -Part One: An Introduction To Ontologies[END_REF]. The components of an ontology, such as rules, classes, properties and individuals, can effectively reflect entities and activities described by the enterprise data model. Both an ontology and a data model can contribute to the meaning of data and to facilitate interoperability, integration, and adaptability of the informational systems that adopt them. Even though an EDM encapsulates the notion of ontology and shares common entities, it lacks the power of fine-grained expressiveness, reasoning and knowledge-based inference capabilities.

In recent years, Big Data [START_REF] Manyika | Big data: The next frontier for innovation, competition, and productivity[END_REF] is used to describe all the new technologies that allow the manipulation of massive amounts of data in order to develop existing business areas or to drive new ones by improving on insight, decision-making and detecting sources of profit. Big Data can be thoroughly described by the following characteristics: Variety (the number of types of data), Velocity (the speed of data generation and processing), Volume (the amount of data) and Value (the knowledge).

In parallel of Big Data evolution, Linked Data [START_REF] Bizer | Linked data -the story so far[END_REF], one of the most widely-used Semantic technologies, constitutes a means to evolve the Web into a global data space. Linked Data was introduced as a set of best practices for publishing and interlinking structured data on the Web by using RDF as the data model and HTTP as the protocol. Even though Linked Data gains its success as a technology by fostering data publication in the WWW, it can also be utilized as an architectural style for integrating either applications or data within the Enterprise.

In the case of Big Data, the Linked Data principles can contribute effectively to the aspect of Variety [START_REF] Mitchell | Linked Data: Connecting and exploiting big data[END_REF] by simplifying data management. For example, data coming from unstructured databases can be linked to data in traditional OLTP and OLAP stores without changing existing schemas.

The interlinking of data following different models (OLAP/OLTP databases, documents, NoSQL etc.) allows more data to be linked and then queried more effectively. So, the context of data expands by achieving more insight as well as better data analysis. The usage of Linked Data in combination with Big Data supports and boosts the fourth V, the Value, too [START_REF] Mitchell | Linked Data: Connecting and exploiting big data[END_REF].

In this work, we make an attempt to gather all the aforementioned aspects, which can leverage the growth of an industry, into one unified approach. Beginning from an EDM, we move to a more semantically enhanced model, an ontology, thus developing the foundation for more efficient consumption of Big Data.

More precisely, we exploit the existing data model for Property and Casualty [START_REF] Jenkins | Property and Casualty Data Model Specification[END_REF], inspired and proposed by the Object Management Group, in order to build an ontology. This ontology meets the needs of and could also be used as the basis for publishing Linked Data in the industry of insurance. The interlinking of data ensures more interoperability as well as sets the infrastructure for adopting Big Data in the Insurance sector.

The usage of an ontology to express the P&C Model as well as any other EDM in the industry may have the following benefits:

-Enhance the existing expressive power of the EDM -Achieve interoperability and extendibility of higher level -Support more efficiently the possibilities of scalability -Accomplish knowledge inference and discovery by exploiting the reasoning power -Bridge the gap between any other subsystems (different kinds of data storage, databases, documents etc.) in the industry without negating the benefits of conventional stores or NoSQL databases The rest of this paper is organized as follows. In Section 2, we start by providing some broad definitions and discussing the concepts of OMG's Property and Casualty Model. Furthermore, in Section 3, we explain in detail the entire process of converting the terms of data model into ontology components. Next, Section 4 outlines an indicative application scenario in order to illustrate the ontology. Finally, Section 5 summarizes our conclusions.

OMG's Property and Casualty Model

The Object Management Group (OMG) [START_REF]The Object Management Group (OMG)[END_REF] has developed a property-casualty insurance enterprise data model with the contribution of representatives from many carriers and using experts in each subject area. The P&C data model [START_REF] Jenkins | Property and Casualty Data Model Specification[END_REF] addresses the data management needs of the Property and Casualty (P&C) insurance community. OMG's Model Driven Architecture principles and related standards have been utilized in order to construct the data model. Also, existing P&C industry standards (e.g., IBM's IAA) have been picked out as a source for the proposed P&C Business Glossary and associated models.

There are plenty of benefits for the organizations that decide to incorporate this data model into their procedures. P&C data model can provide significant value during a wide variety of warehousing, business intelligence, and data migration projects. In addition, these models can be leveraged to improve the use of data and in support of data governance within the enterprise.

Among the components of the P&C data model, there are the entities, attributes and relationships. Due to lack of space, only a snippet of all these is presented in this work. The main objects of the data model are the Entities. An Entity represents a person, organization, place, thing, or concept of interest to the enterprise. Next, an Entity can express a very broad and varied set of instance data, or it can be very specific. This is referred to as levels of abstraction. Some entities that have been used for the application scenario described in Section 4 are listed below.

-Insurable Object: An Insurable Object is an item which may be included or excluded from an insurance coverage or policy, either as the object for which possible damages of the object or loss of the object is insured, or as the object for which damages caused by the object are insured. Examples: residence, vehicle, class of employees. -Vehicle: A Vehicle is an Insured Object that is a conveyance for transporting people and/or goods. -Person: Person can be a human being, either alive or dead.

-Organization: An Organization is a Party that is a business concern or a group of individuals that are systematically bound by a common purpose.

Organizations may be legal entities in their own right. Examples: commercial organizations such as limited companies, publicly quoted multinationals, subsidiaries.

-Agreement: Agreement is language that defines the terms and conditions of a legally binding contract among the identified parties, ordinarily leading to a contract. Examples; policy, reinsurance agreement, staff agreement. -Claim: Claim is a request for indemnification by an insurance company for loss incurred from an insured peril or hazard. -Claim Amount: Claim Amount is the money being paid or collected for settling a claim and paying the claimants, reinsurers, other insurers, and other interested parties. Claim amounts are classified by various attributes. -Claim Folder: A Claim Folder is the physical file in which all claim documents are maintained. -Claim Document: Claim Document is written information such as agreements, financial statements, offers, proposals, etc., to provide backup and depth to agreed-upon or discussed claim matters. -Claim Offer: A Claim Offer is a proposal made by an insurer to a claimant or third party in order to settle a claim.

- There may be multiple results for one assessment. -Fraud Assessment: Fraud Assessment is a subtype of Assessment Result that identifies whether fraud has occurred or is occurring, the extent and impact of the fraud, and to determine who is responsible for the fraud. Α Relationship should be a verb or a verb phrase that is always established between two entities, the 'Parent Entity' and the 'Child Entity'. The relationship is used in order to form a sentence between its two entities. Moreover, the type of relationship can be 'Identifying', 'Non-identifying' or 'Subtype'. Each relationship can be also characterized by the notion of cardinality. For example, the 'Subtype' relationship has always 'Zero-to-one' cardinality. Table 1 presents the majority of the relationships between the entities that are described above and utilized in the usage scenario of Section 4.

Table 1. P&C relationships definitions for the entities of Section 4.

Attributes are usually defined within an entity and is considered as a property or descriptor of this entity. An attribute is meaningless by itself. For example, date of birth comes from the context of the entity to which it is assigned, for example, date of birth of an employee. Every attribute in a data model is connected to a domain that Based on these, a series of business requirements can be represented in the form of logical rules or axioms that can be used to automatically infer possible added-value knowledge [START_REF] Hitzler | Ontologies and Rules[END_REF]. For example, a rule can be imposed stating that if a Driver has been involved in more than e.g. 5 insurance claims within a certain time interval, then he is susceptible to FraudAssesment to be performed on him.

Conclusion and Future Work

In this work, we have shown the feasibility and benefits of adopting a semantic approach towards Big Data manipulation in the insurance sector. To our knowledge, this is the first attempt to express the OMG P&C Model in the form of an OWL 2 ontology, so that reasoning-based conclusions can be enabled. As such, the addedvalue of adopting (even part of) the model at the insurance sector is leveraged, as it can be used towards automating standard legacy processes, such as fraud detection. Instead of manual resolution, an OWL 2 ontology can be used to highlight possible cases that need further investigation.

On the other hand, the specification of a relaxed ontology schema can serve as a scaffold for implementing Linked Data publishing and dissemination of insurance agreement and claim information. In this manner, the information flow between insurance companies, agents and insurers can be streamlined, by automatically transmitting messages through compatible services.

It is expected that contemporary insurance companies would have to deal with a great deal of such information, such resulting in an increased volume and velocity of data. It is our belief that Semantic Web technologies can stand up to these requirements, by establishing a scalable infrastructure around a semantic repository [START_REF] Solomou | A Mashup Personalization Service based on Semantic Web Rules and Linked Data[END_REF], [START_REF] Koutsomitropoulos | Developing Distributed Reasoning-Based Applications for the Semantic Web[END_REF] that secures performance without sacrificing the added-value inference capabilities inherently are equipped with.

Figure 1

 1 Figure 1 illustrates how Insurable Object, Vehicle, Claim and Claim Folder entities can be defined in terms of attribute and can be linked to each other via relationships in the context of P&C data model

Fig. 1 .

 1 Fig. 1. A snippet of the P&C data model.

Fig. 3 .

 3 Fig. 3. Usage scenario for Insurance of Vehicle and Fraud Detection.

  Party Role: Party Role defines how a Party relates to another entity. Role is the definition of what a Person, Organization, or Grouping DOES whereas Relationship is about what a party IS. -Policy Coverage Detail: Policy Coverage Detail defines the coverages included in an insurance policy (refer to Coverage definition). It is a key link in the data model among Policy, Claim, and Reinsurance. -Assessment: Assessment is a formal evaluation of a particular person, organization, or thing that enables business decisions to be made. Examples: Credit Score, Underwriting Evaluation, Medical Condition. -Assessment Result: An Assessment Result is the outcome of the assessment.

Table 2 .

 2 names, data types, lengths, value sets, and validity rules. The main elements in order to define an attribute for an entity are the Attribute Name, Entity Name and Data Type. Table2presents some of the attributes for the entities Insurable Object and Vehicle. Attributes for the entities Insurable Object and Vehicle.

	Parent Entity Name Parent	to	Child	Relationship	Child Entity Name
		Phrase			Cardinality
	Insurable Object	is covered as defined	One-to-Zero-One-or-	Policy	Coverage
		in			More	Detail
	Insurable Object	involved in		Zero-or-One-to-Zero-	Claim
					One-or-More
	Assessment	results in			Zero-or-One-to-Zero-	Assessment Result
					One-or-More
	Claim	documented in		One-to-Zero-One-or-	Claim Folder
					More
	Claim	settlement results in One-to-Zero-One-or-	Claim Amount
					More
	Claim Folder	contains			One-to-Zero-One-or-	Claim Offer
					More
	Claim Folder	contains			One-to-Zero-One-or-	Claim	Folder
					More	Document
	Claim Offer	results in			Zero-or-One-to-Zero-	Claim Amount
					One-or-More

P&C Model as Ontology

In this section, we describe how the Property and Casualty model can be expressed in terms of an ontology using the Web Ontology Language (OWL) [START_REF] Bechhofer | OWL Web Ontology Language Reference[END_REF]. Having the conceptual data model as a reference, we present how data entities representing most of P&C insurance business processes can be converted into ontology components. Note that the reverse is also feasible, i.e. the logical models can be generated from OWL ontologies. According to InfoSphere Data Architect guidelines [START_REF] Soares | IBM InfoSphere: A Platform for Big Data Governance and Process Data Governance[END_REF], we can simply correlate logical data model's data types to OWL data types, logical data model's entities to ontology elements as well as logical data model's relationships to OWL object properties.

In the attempt to design our P&C ontology, we first convert all entities (see Section 2), included in the P&C Data Model, to ontology classes. In detail, the convention adopts the restrictions that are presented in Table 3. All the other types of relationships are represented as object properties in the proposed ontology. Table 3 gathers all the restrictions that must be followed for an effective conversion of these relationships. Two sample relationships, expressed in OWL, are listed below using RDF/XML syntax.

<owl:ObjectProperty rdf:about="http://www.levantes.ceid.upatras.gr/OMG_Insurance# resultsIn"> <rdfs:range rdf:resource="http:// www.levantes.ceid.upatras.gr/OMG_Insurance #AssesmentResult"/> <rdfs:domain rdf:resource="http:// www.levantes.ceid.upatras.gr/OMG_Insurance #Assessment"/> </owl:ObjectProperty> <owl:ObjectProperty rdf:about="http:// www.levantes.ceid.upatras.gr/OMG_Insurance #documentedIn"> <rdfs:domain rdf:resource="http:// www.levantes.ceid.upatras.gr/OMG_Insurance#Claim"/> <rdfs:range rdf:resource="http:// www.levantes.ceid.upatras.gr /OMG_Insurance#ClaimFolder"/> </owl:ObjectProperty> Each entity type will have one or more data attributes. Each attribute of the P&C model has been mapped to a datatype property in the ontology, according to the restrictions in Table 3.

Usage Scenario for Vehicle

A usage scenario (in natural language), relying on the OMG model vocabulary and the implemented ontology, is cited in this subsection. The scenario deals with the case of vehicle insurance and examines the procedure of a fraud assessment. All the nouns, which are in italics, reflect instances of ontology classes. Figure 3 illustrates more thoroughly the usage scenario. Since this is only a snapshot of the model's full range, further refinements are possible.

A vehicle (Vehicle_1) has an insurance (Agreement_1). This vehicle has been insured for a time interval Α with Β amount and Χ coverage (PolicyCoverageDetail_1). The Person_1, having the role of Insurer and being employed by the Organization, Orgabnization_1 has insured the Vehicle_1 via the Agreement_1. The Person_2 is owner of the Vehicle_1. At the same time, the Person_2 has also another role, the role of Driver.

An accident with significant damages occurred. Person_2, the owner of Vehicle_1, is involved in a claim (Claim_1). The Claim_1 is documented in the folder (ClaimFolder_1) which contains two documents (ClaimDocument_1 and ClaimDocument_2) as well as an offer (ClaimOffer_1). The ClaimOffer_1 results in a specific amount, the ClaimAmount_1. An assessment (Assesment_1) has been done for the Claim_1 and results in the FraudAssesment_1.


Roya Golchay

Frédéric Le Mouël

Julien Ponge

Nicolas Stouls

Spontaneous Proximity Clouds: Making Mobile Devices to Collaborate for Resource and Data Sharing

Keywords: Mobile Cloud Computing, Spontaneous Proximity Cloud, Collaborative Application Offloading, Resource Sharing, Decision Cache, Offloading Middleware, Learned-based Decision-Making

The base motivation of Mobile Cloud Computing was empowering mobile devices by application offloading onto powerful cloud resources. However, this goal can't entirely be reached because of the high offloading cost imposed by the long physical distance between the mobile device and the cloud. To address this issue, we propose an application offloading onto a nearby mobile cloud composed of the mobile devices in the vicinity -a Spontaneous Proximity Cloud. We introduce our proposed dynamic, ant-inspired, bi-objective offloading middleware -ACOMMA, and explain its extension to perform a close mobile application offloading. With the learning-based offloading decision-making process of ACOMMA, combined to the collaborative resource sharing, the mobile devices can cooperate for decision cache sharing. We evaluate the performance of ACOMMA in collaborative mode with real benchmarks -Face Recognition and Monte-Carlo algorithms -and achieve 50% execution time gain.

Introduction

Mobile Cloud Computing is the emerging paradigm of recent decades that focuses on overcoming the inherent shortages of mobile devices regarding processing power, memory and battery via application offloading, by total or partial execution of mobile applications on a distant cloud. Hence, the application offloading might not always be helpful because of the long physical distance between the mobile device and the cloud. The concept of the cloudlet [START_REF] Satyanarayanan | The case for vm-based cloudlets in mobile computing[END_REF] has been raised to response to this issue of distance. The cloudlet is a predefined cloud in proximity that consists of some static stations and is generally installed in public domains, but with no guaranty of availability near a mobile device.

As a solution to this cloud distance problem, we propose to offload application onto a Spontaneous Proximity Cloud (SPC) -a cloud in the proximity of the mobile device, composed of a set of mobile devices in the vicinity. This SPC is a collaborative group of moving devices in proximity with members that occasionally join and leave.

The short distance between the mobile device and the SPC overcomes the issue of latency in data transfer to distant clouds, especially in high network traffic conditions. Offloading onto SPC could also prevent imposing bandwidth allocation overhead onto a communication network that experiences a shortage of capacities, due to the continuous traffic growth. Besides, the energy consumption of a 3G cellular data interface, associated with the cloud, is 3 to 5 times much higher than WiFi transmissions, used between mobile devices [START_REF] Cuervo | MAUI: Making smartphones last longer with code offload[END_REF] [START_REF] Miluzzo | Vision: Mclouds -computing on clouds of mobile devices[END_REF]. Another motivating factor to use SPC is the popularity of mobile devices. Inadequate network coverage, natural or man-made disasters may damage the data centres and significant technical failures -such as experimented by Amazon cloud [START_REF] Adem | Crowdsourcing the cloud: Energy-aware computational offloading for pervasive community-based cloud computing[END_REF] -can make remote clouds temporarily unavailable. While, because of the increasing number of mobile devices and the wide frequency of use -per user or household [START_REF] Ahonen | Household penetration rates for technology across the digital divide[END_REF] -a mobile device presents a great chance to be surrounded by a group of mobile devices. Finally, the use of SPC is a perfect incentive for green computing, with individual devices powered under the user responsibility that can use human body kinetic energy harvesting or solar panels [START_REF] Adem | Crowdsourcing the cloud: Energy-aware computational offloading for pervasive community-based cloud computing[END_REF].

We found all these factors motivating enough to design and implement ACOMMA, an Ant-inspired Collaborative Offloading Middleware for Mobile Applications, that performs offloading on either distant cloud or SPC. ACOMMA is an automated offloading middleware that takes offloading decisions dynamically by applying an ant-inspired bi-objective decision-making algorithm. The details of offloading onto distant cloud are already explained and evaluated in our previous article [START_REF] Golchay | Automated Application Offloading through Ant-inspired Decision-Making[END_REF]. In this paper, we demonstrate that taking a decision in a mobile device can benefit to all the other mobile devices in the vicinity and so better the application execution performances. We create a decision cache composed of the execution trails of mobile applications and, by using learning-based decision-making algorithm, ACOMMA could reuse previous offloading decisions instead of running its Ant Colony Optimization (ACO) decision-making algorithm.

In this paper, we focus on the extension of ACOMMA in a way that it can be able to perform offloading in a collaborative manner. In collaborative offloading, instead of communicating with a distant cloud, the mobile device cooperates with SPC's members, for either resource or data sharing. Our main contributions consist of:

-Developing a decision-making process performing multi-destination offloading.

To this end, we need to modify the ACO algorithm to take potential offloading decisions to remote clouds as well as mobile devices in the SPC, without any lock-in considerations to the number of devices. In this case, the mobile devices collaborate for resource sharing. -Developing a learned-based decision-making process to use the collaborative decision cache instead of the local cache. In this case, the mobile devices collaborate for data sharing. They share their local caches to create a richer collaborative cache that permits more efficient and relevant offloading decisions.

The remainder of the paper is structured as follows: Section 2 discusses the existing offloading approaches. Section 3 explains the architecture of our proposed offloading middleware -ACOMMA. Section 4 and 5 show how ACOMMA is enhanced to make mobile devices collaborate for resource and cache sharing. Section 6 evaluates our offloading middleware under a range of scenarios and using different benchmarks. Finally, Section 7 provides a summary, conclusion and outline of future work.

Related work

Recently, delegating total or partial application execution to more powerful machines instead of local devices -known as application offloading -has attracted attention to overcome resource limitations and to save the battery of mobile devices. A significant amount of researches has been performed in this domain to propose solutions to bring the cloud to the vicinity of the mobile device MAUI [START_REF] Cuervo | MAUI: Making smartphones last longer with code offload[END_REF] and ThinkAir [START_REF] Kosta | Thinkair: Dynamic resource allocation and parallel execution in the cloud for mobile code offloading[END_REF] are the most prominent works in this domain. They are focusing on optimising energy consumption or execution time using linear programming. They use the virtual machine migration techniques to execute application methods onto the cloud. However, these virtualized environments are heavy for limited mobile devices. CloneCloud [START_REF] Chun | CloneCloud: Elastic execution between mobile device and cloud[END_REF] is a lighter approach since it cuts the application into two thread level partitions using linear programming, with only one of them offloaded onto the cloud. Some approaches perform offloading onto a closer surrogate, a cloudlet [START_REF] Satyanarayanan | The case for vm-based cloudlets in mobile computing[END_REF], that is composed of static stations. However, a cloudlet does not necessarily exist near a mobile device.

Few studies focused on the use of adjacent mobile devices as offloading surrogates. Transient cloud [START_REF] Penner | Transient clouds: Assignment and collaborative execution of tasks on mobile devices[END_REF] uses the collective capabilities of nearby devices in an ad-hoc network to meet the needs of the mobile device. A modified Hungarian method is applied as an assignment algorithm to assign tasks to devices that are to be run according to their abilities. The execution of each task by any device imposes some cost, and the assignment algorithm aims to find the minimum total cost assignment. To that end, [START_REF] Penner | Transient clouds: Assignment and collaborative execution of tasks on mobile devices[END_REF] has proposed a dynamic cost adjustment to balance the tasks based on costs between devices. Miluzzo et al. [START_REF] Miluzzo | Vision: Mclouds -computing on clouds of mobile devices[END_REF] proposed an architecture named mCloud that runs resource-intensive applications on collections of cooperating mobile devices and discuss its advantages. Kassahun et al. [START_REF] Adem | Crowdsourcing the cloud: Energy-aware computational offloading for pervasive community-based cloud computing[END_REF] have gone one step further and formulated a decision algorithm for global adaptive offloading. They implemented the program components on mobile devices set to optimise Time to Failure (TTF) while taking into account the limitations of the effectiveness of the program. Having highlighted the benefits of collaboration for mobile task offloading, Mtibaa et al. also implemented computational offloading schemes to maximise the longevity of mobile devices [START_REF] Mtibaa | Collaborative mobile-to-mobile computation offloading[END_REF] [START_REF] Mtibaa | Towards resource sharing in mobile device clouds: Power balancing across mobile devices[END_REF].

The general architecture of ACOMMA

The proposed architecture of ACOMMA makes application offloading possible onto remote clouds and SPC as a single or multiple destination offloading process. The building blocks of ACOMMA are illustrated in Figure 1.

ACOMMA considers a mobile application as a dependency graph, where the nodes represent the function/method calls of the application and the edges are their dependency in terms of function/method invocations. The offloading decision-making process partitions this call graph to define which function/method should be executed locally -on the mobile device, near-remotelyon a device of the SPC, or far-remotely -on the distant cloud. The offloading middleware is composed of a group of services to offload this application. The Offloading Manager is in charge of taking offloading decisions using (1) an Ant Colony Optimization algorithm for the initial decision-making or (2) String matching algorithm for learning-based decision-making. In the learning-based mode, the decision-making relies on previous application execution traces, saved in a local or collaborative decision cache. Coming to the collaborative mode, the Collaboration Service takes the responsibility of offloading onto SPC with the help of Offloading Manager. The Collaboration Service makes nearby devices collaborate using the neighbours' information prepared by the Discovery Service. This service finds the nearby devices and saves their address and information. To perform a dynamic offloading considering the cur-rent state of mobile devices, ACOMMA needs to be aware of current conditions and requirements. The mobile devices' information, such as the available battery and memory, and their environment such as the available networks, the available bandwidth, as well as cloud kind and theirs costs, are collected by Context Monitoring Service. This contextual information helps ACOMMA to choose in-between the SPC or the remote clouds.

Collaborative resource sharing in application offloading

As mentioned before, the decision-making process of ACOMMA is based on the application call graph partitioning. To perform offloading onto SPC, the decision engine breaks apart the application into several parts -instead of two in traditional partitioning approaches, where each part represents an executing device. For example, Figure 2 shows the partitioning for offloading onto three nearby devices, where nodes a, c, f execute locally, node b executes on device A, node e and g execute on device B and finally mobile device C executes node d.

Fig. 2. Application partitioning for multi destination offloading

To perform such a graph partitioning for multi-destination offloading, the ACOMMA collaboration service modifies the application call graph in a way that for each method, several nodes are added to the graph, depending on the number of potential executing devices, one for each device. The modification process of the call graph is shown in the Figure 3.

The original graph is composed of three nodes, where the start and end nodes (node 1 and 3) have to execute locally. Assuming that there are two devices in SPC in addition to the current mobile device, the node 2 is then duplicated two times -as often as the number of possible execution targets. The ACOMMA decision engine partitions the graph using an ACO algorithm that finds the shortest path between the start and end points of the graph. The choice of the first path shows the local execution of method 2 on device A, where the choice of the second and the third path represents the execution of method 2 on device B and device C respectively. Finding shortest path is done according to weights assigned to the edges of the graph. Since the different devices can have different optimisation goals, to reach a consensus in the objective function, we apply a multi-objective decision-making process -illustrated by a bi-objective decision-making with the execution cost of the related method regarding CPU usage and execution time.To take dynamic offloading decisions based on the current state, the shortest path is calculated for each function/method call in the total graph.

Collaborative decision cache sharing

Learning is one of the functions of dynamic systems -such as in sensor networks and mobile networks. It is mainly used for the establishment of a relevant situation and the adaptations to the environment. In existing SPC, the learning process stays local. We argue that, when a mobile device takes a decision, this decision could benefit to the other devices nearby.

To distribute the local decisions, we rely on a sharing decision cache. The sharing decision cache between nearby devices makes collaborative decisions possible. In this learning-based decision-making process, the mobile devices in the same state and environmental conditions could perform offloading in the same way as their neighbours. Moreover, even if the execution conditions are not exactly the same, in case of common applications, the decision is relevant enough.

To take collaborative decisions, the collaborative cache is created by merging local cache of nearby devices. They could receive and send respecting different dissemination, merging and invalidating policies. For receiving neighbour's local decisions, we propose on-demand, periodical and on-change policies. Using an on-demand method, a mobile device broadcasts a cache request to the nearby devices whenever needed. In the periodic method, each mobile device periodically sends their decision caches to their neighbours without any concerns about their requirement. Also, in the on-change method, the source device sends its decision cache whenever it is modified either by adding a new execution trail or deleting old ones. The merge could be done simply by adding the new executing trail at the end of the local cache. Alternatively, another way is to implement a collaborative cache with unique rows by deleting the duplicate traces. Creating a weighted cache is also an implementation available. The weight of each executing trace corresponds to the number of decisions already taken -implying that an already optimisation decision have more chance to be reselected. As cache invalidation policies, we propose periodic and on-change methods. While the offloading decisions highly depend on the current status of the mobile device itself and its environment, the cache could reset when these conditions change.

Applying different combinations of these policies for cache management may greatly impact the performance of ACOMMA for offloading using collaborative decision-making.

6 Implementation and evaluations

Benchmark applications and experimental platform

To evaluate the performance of ACOMMA, we first test micro-benchmarks mathematical functions: Matrix determinant and Integral -consuming enough resources to make offloading valuable. Their small number of methods helps us to trace function call executions accurately. To be closer to real applications, we also implement macro-benchmarks with popular offloading applications of Chess and Face Recognition including Monte Carlo and Eigenfaces algorithms [START_REF]Face recognition algorithm[END_REF].

As mobile devices, we use Samsung Galaxy SII with 1,2 GHz dual-core processor and 2GB of memory running Android version 4.1.2 (Jelly Bean) and Asus Google Nexus 7 pad with quad-core 1.2 GHz processor and 1GB of memory running Android version 5.1.1 (Lollipop). To successfully validate collaborative offloading of ACOMMA using SPC, we need to show that ACOMMA can detect the SPC and correctly dispatch the methods of running application between detected nearby devices according to their processing power.

Results

To evaluate the efficiency of offloading onto the SPC, we apply a scenario where a Galaxy SII makes offloading onto an SPC that consists in 2 Galaxy SII and 3 Google Nexus 7 pads. We compare the performance of offloading onto this SPC with offloading onto a MacBook Pro with 8 GB of memory, a 250 GB hard disk and a 2,53 GHz Intel processor dual-core as a remote server. This server has OS X 10.9.5 Mavericks as operating system. The result shows that the local execution is rather slow -1200ms for the Monte Carlo application, and offloading onto the MacBook presents a significant gain in terms of execution time -60-70ms [START_REF] Golchay | Automated Application Offloading through Ant-inspired Decision-Making[END_REF]. Offloading to the SPC -less powerful than a remote cloud, but with a better latency -results in a less efficient execution time -100ms, but interesting enough to test the benefit of a collaborative cache.

Coming to the evaluation of dispatching onto SPC, we ran Determinant and Integral 10 times with a SPC composed of four devices in addition to the source show the percentage of successful offloading for each application method. Considering the four methods of Integral benchmark, the method D is never offloaded. Considering the five methods of Determinant, method B and method C were always executed locally. These are the methods that consume a negligible amount of resources, when offloading them impose more cost to the system compared to their local execution. shows the offloading proportion and the contribution of each device to the offloading process. As expected, in most of the cases the device D4 has the lighter portion of execution as it is the less powerful device. The devices D1, D2 and D3 that have the same hardware characteristics, have almost the same execution contribution, even if their loads are not exactly equal. These results show that ACOMMA is really context-and application-aware to make multi-destination offloading and to dispatch the application methods between SPC's members correctly.

To evaluate the sharing benefits, we compare the execution time of the different benchmarks between ACO and string matching based on a local cache [START_REF] Golchay | Automated Application Offloading through Ant-inspired Decision-Making[END_REF] and the collaborative cache. We evaluate the decision-making based on the collaborative cache with an on-changed dissemination policy, and a unique weighted cache merge policy (the invalidating policy has been shown to have a neglectable impact on results [START_REF] Golchay | Automated Application Offloading through Ant-inspired Decision-Making[END_REF]). We run Determinant, Integral, Face detection and Monte-Carlo 10 times for two series of inputs on Galaxy SII. First, the ACO algorithm offloads and populates the local cache with maximum 10 rows. Secondly, when the source device has finished its executions, we run the same application on destination devices while making the offloading decision using collaborative cache and a string matching algorithm. The results in Figure 6 show that learning-based decision-making using a collaborative cache is more efficient than using a local cache. The gain in terms of execution time depends on the graph size. Small applications -Determinant and Integral -presents 30-40% gain (10ms) and more complex ones -Face Recognition and Monte Carlo -up to 60% (35ms).

Conclusion and future work

In this work, we propose the Spontaneous Proximity Cloud concept to offload applications onto mobile devices in the vicinity. We enriched our ant-inspired bi-objective offloading middleware, ACOMMA, with a learning-based decisionmaking using a collaborative resource and data cache sharing. We evaluate the performance of ACOMMA in collaborative mode with real benchmarks -Face Recognition and Monte-Carlo algorithms -and achieve 50% execution time gain. Several issues need further work. Testing the robustness and the scalability of the

Fig. 1 .

 1 Fig. 1. The general architecture and building blocks of ACOMMA

Fig. 3 .

 3 Fig. 3. Call graph modification for multi destination offloading

Fig. 4 .

 4 Fig. 4. Successful method offloading rate(%)

Fig. 5 .

 5 Fig. 5. Contribution of devices to execute offloaded methods(%)

Fig. 6 .

 6 Fig. 6. Learned based offloading using local and collaborative cache

offloading to the mobility and connection interferences is a major one. A balance between the caching cost -storage and network -and the better decision to take has to be carefully studied.


Claude-Pierre Jeannerod
email: claude-pierre.jeannerod@inria.fr

Siegfried M Rump
email: rump@tuhh.de

ON RELATIVE ERRORS OF FLOATING-POINT OPERATIONS: OPTIMAL BOUNDS AND APPLICATIONS

Keywords:

Rounding error analyses of numerical algorithms are most often carried out via repeated applications of the so-called standard models of floating-point arithmetic. Given a round-to-nearest function fl and barring underflow and overflow, such models bound the relative errors

| by the unit roundoff u. This paper investigates the possibility and the usefulness of refining these bounds, both in the case of an arbitrary real t and in the case where t is the exact result of an arithmetic operation on some floating-point numbers. We show that E 1 (t) and E 2 (t) are optimally bounded by u/(1 + u) and u, respectively, when t is real or, under mild assumptions on the base and the precision, when t = x ± y or t = xy with x, y two floating-point numbers. We prove that while this remains true for division in base β > 2, smaller, attainable bounds can be derived for both division in base β = 2 and square root. This set of optimal bounds is then applied to the rounding error analysis of various numerical algorithms: in all cases, we obtain significantly shorter proofs of the best-known error bounds for such algorithms, and/or improvements on these bounds themselves. November 3, 2016.

Introduction

Given two integers β, p 2, let F be the associated set of floating-point numbers having base β, precision p, and no restriction on the exponent range:

F = {0} ∪ {M • β e : M, e ∈ Z, β p-1 |M | < β p }.
Let also fl : R → F denote any round-to-nearest function, such that (1.1) |t -fl(t)| = min

f ∈F |t -f |, t ∈ R.
In particular, no specific tie-breaking strategy is assumed for the function fl. Two relative errors can then be defined, depending on whether the exact value or the rounded value is used to divide the absolute error in (1.1): the error relative to t is

E 1 (t) = |t -fl(t)| |t| if t = 0,
while the error relative to fl(t) is

E 2 (t) = |t -fl(t)| |fl(t)| if fl(t) = 0.
(In each case the relative error may be defined to be zero if the denominator is zero: the exponent range being unbounded, fl(t) = 0 implies t = 0, so in both cases a zero denominator means that no error occurs when rounding t.)

For rounding error analysis purposes, the most commonly used bounds are E 1 (t) u and E 2 (t) u, where

u = 1 2 β 1-p
is the unit roundoff associated with fl and F, and such bounds are typically handled via the so-called standard models fl(t) = t(1 + δ 1 ) = t/(1 + δ 2 ), |δ 1 |, |δ 2 | u; see [5, pp. 38-39]. It is also known that the bound on the first relative error can be refined slightly [12, p. 232], 1 so that

(1.2) E 1 (t) u 1 + u and E 2 (t) u.
These worst-case bounds hold for any real number t and any rounding function fl. Furthermore, they can be regarded as optimal in the sense that each of them is attained for some pair (t, fl) with t expressed in terms of β and p: since 1 + u is exactly halfway between the two consecutive elements 1 and 1 + 2u of F, we have E 1 (1 + u) = u/(1 + u) and, assuming further that fl rounds ties "to even,"

E 2 (1 + u) = u.
In this paper, we investigate the possibility and the usefulness of refining the bounds in (1.2) when t is not just an arbitrary real number but the exact result of an operation on some floating-point number(s), that is, when t = x op y,

x, y ∈ F, op ∈ {+, -, ×, /} : F × F → R as well as t = √ x. Our first contribution is to establish optimal bounds on both E 1 and E 2 for each of these five basic operations, as shown in Table 1.

u x/y u -2u 2 if β = 2, u 1+u if β > 2 u-2u 2 1+u-2u 2 if β = 2, u if β > 2 √ x 1 -1 √ 1+2u √ 1 + 2u -1
As we shall see later in the paper, each of these bounds is attained for some explicit input values in F and rounding functions fl, possibly under some mild (necessary and sufficient) conditions on β and p. Specifically, for addition, subtraction, and multiplication the condition for optimality is that β is even, and in the case of multiplication in base 2 it is that 2 p + 1 is not a Fermat prime. In most practical situations such conditions are satisfied and thus the general bounds in (1.2) remain the best ones for floating-point addition, subtraction, and multiplication; as Table 1 shows, this is also the case of division in any base larger than 2. In contrast, for division in base 2 and for square root, the general bound u/(1+u) ≈ u-u 2 on E 1 can be decreased further to u-2u 2 and to 1-(1+2u) -1/2 ≈ u- 3 2 u 2 , respectively; likewise, the general bound u on E 2 can be decreased to (u

-2u 2 )/(1 + u -2u 2 ) ≈ u -3u 2 and (1 + 2u) 1/2 -1 ≈ u -1 2 u 2 .
Our second contribution is to show that in the context of rounding error analysis of numerical algorithms, applying these optimal bounds in a systematic way leads to simpler and sharper bounds, and/or to more direct proofs of existing ones.

In particular, this allows us to establish the following three new error bounds:

• For the summation of n floating-point numbers x 1 , . . . , x n (using n -1 floating-point additions and any ordering), we show that the resulting floating-point approximation s satisfies

(1.3) s - n i=1 x i n-1 i=1 |e i | (n -1)u 1 + u n i=1 |x i |,
where |e i | denotes the absolute error of the ith floating-point addition. • For the summation of n real numbers x 1 , . . . , x n , we show that by first rounding each x i into fl(x i ) and then summing the fl(x i ) in any order, the resulting approximation s satisfies

(1.4) s - n i=1 x i n i=1 |d i | + n-1 i=1 |e i | ζ n n i=1 |x i |, ζ n < nu,
where the d i are given by d i = x i -fl(x i ) and the e i are as before. • For the Euclidean norm of a vector of n floating-point numbers x 1 , . . . , x n we show that summing the squares in any order and then taking the square root of the result yields a floating-point number r such that

(1.5) r = n i=1 x 2 i 1/2 • (1 + ), | | (n/2 + 1)u.
Note that each of these bounds holds without any restriction on n. The bounds in (1.3) and (1.4) improve upon the best previous ones, from [START_REF] Jeannerod | Improved error bounds for inner products in floating-point arithmetic[END_REF], in two ways: they are sharper and apply not only to the absolute error of s but also to the sum of the absolute local errors. Furthermore, we will see that the new bound in (1.3) implies the one in (1.4) almost immediately; in other words, using (1.3) allows us to recover the constant nu established in [START_REF] Jeannerod | Improved error bounds for inner products in floating-point arithmetic[END_REF]Proposition 4.1] for sums of n reals (and thus n-dimensional inner products as well), but in a much more direct way. Finally, the bound in (1.5) nicely replaces the expression (n/2 + 1)u + O(u 2 ) that would result from using the suboptimal bound E 1 ( √ x) u. Besides the evaluation of sums and norms, and to illustrate further the benefits of applying the refined bounds in Table 1, we provide four other typical examples of rounding error analysis. These examples deal with small arithmetic expressions, minors of tridiagonal matrices, Cholesky factorization, and complex floating-point multiplication. We shall see that in each case the existing error bound can be either replaced by a simpler and sharper one, or recovered via a significantly shorter proof.

Notation and assumptions. All our results hold under the customary assumption that β, p 2. Furthermore, following [START_REF] Higham | Accuracy and Stability of Numerical Algorithms[END_REF] (and unless stated otherwise) we shall ignore underflow and overflow by assuming that the exponent range of F is unbounded. Finally, the common tool used to establish all the error bounds in Table 1 is the function ufp : R → F 0 from [START_REF] Rump | Accurate floating-point summation part I: Faithful rounding[END_REF], called unit in the first place (ufp) and defined as follows: ufp(0) = 0 and, if We summarize our discussion in the theorem below. Although the bounds given there already appear in [18, p. 74] and [12, p. 232] for E 1 , and in [START_REF] Higham | Accuracy and Stability of Numerical Algorithms[END_REF]Theorem 2.3] for E 2 , the characterization of their attainability does not seem to have been reported elsewhere.

Theorem 2.1. If t ∈ R\{0}, then E 1 (t) u 1 + u and E 2 (t) u.
Furthermore, the bound on E 1 is attained if and only if |t| = (1 + u)ufp(t), and the bound on E 2 is attained if and only if |t| = (1 + u)ufp(t) and |fl(t)| = ufp(t).

Optimal error bounds for floating-point operations

We establish here optimal bounds on both E 1 and E 2 for the operations of addition, subtraction, multiplication, fused multiply-add, division, and square root.

3.1. Addition, subtraction, and fused multiply-add. When t has the form t = x + y with x, y in F, we show in the theorem below that the general bounds

E 1 (t) u 1+u and E 2 (t) u given in (1.
2) remain optimal unless the basis β is odd. This extends the analysis done by Holm [START_REF] Holm | Floating-Point Arithmetic and Program Correctness Proofs[END_REF], who considers only the first relative error and assumes implicitly that the basis is even. Theorem 3.1. Let β, p 2 and t = x + y with x, y ∈ F. The bounds in (1.2) are optimal if and only if β is even. Furthermore, when β is even, they are attained for (x, y) = (1, u) and rounding "to nearest even."

Proof. If β is odd, then u = 1 2 β 1-p = ∞ i=0 β-1
2 β -i-p with β-1 2 ∈ {1, . . . , β -1}, so u and 1 + u have infinite expansions in base β. Hence x + y cannot have the form ±(1 + u)β e with e ∈ Z and thus, by Theorem 2.1, equality never occurs in the bounds E 1 (x + y) u/(1 + u) and E 2 (x + y) u.

If β is even, then u is in F. Consequently, we can take (x, y) = (1, u), which gives E 1 (x + y) = u/(1 + u) and, for ties rounded "to even", E 2 (x + y) = u.

Since 1 + 2u belongs to F for any β and since 1 + u = (1 + 2u) -u = 1 × 1 + u, the theorem above extends immediately to subtraction as well as to higher-level operations encompassing addition, like the fused multiply-add (x, y, z) → fl(xy +z).

3.2.

Multiplication. When t = xy with x, y ∈ F, the theorem below shows that the situation is more subtle than for addition: although the condition that β is even remains necessary for the optimality of the bounds E 1 (t) u/(1 + u) and E 2 (t) u, it is sufficient only when β = 2; when β = 2, optimality turns out to be equivalent to 2 p + 1 being composite. Theorem 3.2. Let β, p 2 and t = xy with x, y ∈ F. We then have the following, depending on the value of the base β:

• If β = 2, then the bounds in (1.2) are optimal if and only if 2 p + 1 is not prime; furthermore, if D is a non-trivial divisor of 2 p +1, then these bounds are attained for

(x, y) = (2 + 2u)ufp(D) D , D ufp(D)
and rounding "to nearest even."

• If β > 2, then the bounds in (1.2) are optimal if and only if β is even, and when the latter is true these bounds are attained for

(x, y) = (2 + 2u, 2 -1 )
and rounding "to nearest even."

Before proving this result, note that the attainability of the bound E 1 (xy) u/(1 + u) has been observed in [6, p. 10] in the particular case (β, p) = (2, 5), by taking x and y in the form shown above with D = 11.

Proof. By Theorem 2.1, the optimality of the bounds in (1.2) when t = xy is equivalent to the existence of a pair (x, y) ∈ F × F such that |xy| = (1 + u)ufp(xy).

Assume first that β > 2. Similarly to Theorem 3.1, a necessary condition for optimality is that β be even. Furthermore, if β is even, then both 2 + 2u and 2 -1 are in F, and since their product equals 1+u, it suffices to take (x, y) = (2+2u, 2 -1 ) to show that the bounds in (1.2) are optimal.

Let us now consider the case β = 2. Since ufp(t • 2 e ) = ufp(t) • 2 e for all (t, e) ∈ R × Z, we can assume with no loss of generality that 1

x, y < 2. This implies that ufp(xy) ∈ {1, 2} and, since x, y ∈ {1, 1 + 2u, 1 + 4u, . . .} and u > 0, that the product xy cannot be equal to 1 + u. Hence, optimality is equivalent to the existence of x, y

∈ F ∩ [1, 2) such that xy = 2 + 2u, that is, equivalent to the existence of integers X, Y such that (3.1) XY = (2 p + 1) • 2 p-1 and 2 p-1 X, Y < 2 p .
If 2 p + 1 is prime, then either X or Y must be larger than 2 p , so (3.1) has no solution.

If 2 p +1 is composite, one can construct a solution (X 0 , Y 0 ) to (3.1) as follows. Let D denote a non-trivial divisor of 2 p +1, and let X 0 = 2 p +1 D ufp(D) and Y 0 = D 2 p-1 ufp(D) . Clearly, X 0 is an integer and the product X 0 Y 0 has the desired shape. Thus, it remains to check that Y 0 ∈ Z and that both X 0 and Y 0 are in the range [2 p-1 , 2 p ). Since 2 p + 1 is odd, D must be odd too, which implies that

(3.2) ufp(D) + 1 D < 2ufp(D) and D < 2 p .
Consequently, ufp(D) 2 p-1 , so that ufp(D) divides 2 p-1 and Y 0 is an integer. Furthermore, (3.2)

leads to 2 p-1 < 2 p +1 2 < X 0 (2 p + 1)(1 -1 D ) < 2 p and 2 p-1 < Y 0 < 2 p ,
so that X 0 and Y 0 satisfy the range constraint in (3.1).

Finally, multiplying X 0 and Y 0 by 2u = 2 1-p gives x 0 = (2 + 2u)ufp(D)/D and

y 0 = D/ufp(D) in F ∩ [1, 2) and such that x 0 y 0 = 2 + 2u = (1 + u)ufp(x 0 y 0 ).
In the rest of this section, we show that the optimality condition "2 p + 1 is not prime" arising in Theorem 3.2 for radix two is in fact satisfied in most practical situations.

First of all, if p is not a power of two, this condition is well known to hold [3, Exercise 18, §4], since p can be factored as p = mq with q odd and then

(3.3) 2 p + 1 = (2 m + 1) 2 p-m -2 p-2m + • • • -2 m + 1 .
The binary basic formats specified by the IEEE 754-2008 standard being such that p ∈ {24, 53, 113}, they fall into this category. More precisely, since here p is either odd or a multiple of three, we deduce from (3.3) explicit divisors of 2 p + 1 and thus explicit pairs (x, y) ∈ F 2 for which the bounds in Theorem 3.2 are attained:

• If p is odd, then 3 divides 2 p + 1 and we can take (x, y) = 4+4u 3 , 3 2 ; • If p ≡ 0 mod 3, then 2 p + 1 can be factored as (2 p/3 + 1)(2 2p/3 -2 p/3 + 1), so we can take (x, y) = (2 -2u 1/3 + 2u 2/3 , 1 + u 1/3 ).

In fact, the sufficient condition "p is not a power of two" is satisfied not only by those basic formats but also by all the binary interchange formats of IEEE 754-2008, for which either p ∈ {11, 24, 53, 113} or

(3.4) p = k -d + 13 with d = 4 log 2 k , k = 32j, j ∈ N 5 ,
and where • denotes rounding to a nearest integer. (A proof of the fact that (3.4) implies that p is not a power of two is deferred to Appendix A.) Assume now that p is a power of two. In this case 2 p + 1 is not prime if and only if it is not a prime number of the form F = 2 2 + 1, called a Fermat prime. Currently, the only known Fermat primes are F 0 , F 1 , F 2 , F 3 , F 4 and, on the other hand, F is known to be composite for all 5 32; see for example [START_REF] Keller | Prime factors k • 2 n + 1 of Fermat numbers Fm and complete factoring status[END_REF][START_REF] Sloane | Sequence A019434, The On-Line Encyclopedia of Integer Sequences[END_REF]. To summarize, the only values of p for which the optimality condition "2 p + 1 is not prime" can fail to be satisfied are 2, 4, 8, 16 and p = 2 2 33 ≈ 8.6 × 10 9 , and none of these values corresponds to an IEEE format.

3.3.

Division. This section focuses on the largest possible relative errors committed when rounding x/y with x, y nonzero elements of F. As the theorem below shows, the general bounds E 1 (t) u 1+u and E 2 (t) u given in (1.2) can be refined further for base 2, but remain optimal for all other bases. Note that unlike for addition or multiplication, optimality is achieved without any extra assumption on the parity of β or the number theoretic properties of p. Theorem 3.3. Let β, p 2 and let x, y ∈ F be nonzero. Then

E 1 (x/y) u -2u 2 if β = 2, u 1+u if β > 2,
and

E 2 (x/y) u-2u 2 1+u-2u 2 if β = 2, u if β > 2.
The bounds for β = 2 are attained at (x, y) = (1, 1 -u) and, assuming ties are rounded "to even", the bounds for β > 2 are attained at (x, y) = (2 + 2u, 2).

Proof. When β > 2 the bounds are the general ones given in (1.2), and the fact they are attained for division follows immediately from 2 + 2u ∈ F. The rest of the proof is thus devoted to the case β = 2. Let t = x/y. Since t cannot be a midpoint [START_REF] Markstein | Computation of elementary functions on the IBM RISC System/6000 processor[END_REF][START_REF] Jeannerod | Midpoints and exact points of some algebraic functions in floating-point arithmetic[END_REF], we have fl(-t) = -fl(t) and fl(t • 2 e ) = fl(t) • 2 e , e ∈ Z, regardless of the tie-breaking rule of fl. Consequently, we can assume 1 t < 2 and x, y > 0. When t = 1 both E 1 and E 2 are zero, so we are left with handling t such that 1 < t < 2.

The lower bound on t implies x > y, which for x and y in F is equivalent to x y + 2u ufp(y). Hence, using y (2 -2u)ufp(y), (3.5) t 1 + 2u ufp(y)

y 1 + u 1 -u = 1 1 -u .
Since 1/(1 -u) is strictly larger than the midpoint 1 + u, it follows that (3.6) fl(t) ∈ {1 + 2u, 1 + 4u, . . .}.

Assume for now that p 3. (For simplicity, the case β = p = 2 is handled separately at the end of the proof.)

If fl(t) 1+4u then t 1+3u, so that E 1 (t) u ufp(t)/t u/(1+3u) < u-2u 2 for p 3. Similarly, E 2 (t) u/(1 + 4u) < (u -2u 2 )/(1 + u -2u 2 ) for p 3.

If fl(t) = 1 + 2u then, recalling (3.5) and the fact that t is not a midpoint,

(3.7) 1 1 -u t < 1 + 3u.
We now distinguish between the following two sub-cases, depending on how t compares to fl(t) = 1 + 2u:

• If t 1 + 2u, then E 1 (t) = (1 + 2u)/t -1 and E 2 (t) = 1 -t/(1 + 2u
), so that the first inequality in (3.7) gives immediately the desired bounds, which are attained only when t = 1/(1 -u); since both 1 and 1 -u are in F when β = 2, this value of t is obtained for (x, y) = (1, 1 -u).

• If t > 1 + 2u, then E 1 (t) = 1 -(1 + 2u)/t and E 2 (t) = t/(1 + 2u) -1. The bound t < 1 + 3u from (3.7) then gives immediately E 1 (t) < u/(1 + 3u),
which is less than u -2u 2 for p 3. For E 2 (t), however, using t < 1 + 3u is not enough and we show first how to replace this bound by the slightly sharper one

(3.8) t 2 + 7u 2 + u = 1 + 3u -3 2 u 2 + O(u 3 ).
The range of t implies y +2u ufp(y) < x < y +6u ufp(y). Note that y cannot be equal to (2 -2u)ufp(y), for otherwise 2ufp(y) < x < (2 + 4u)ufp(y), thus contradicting the fact that x ∈ F. Therefore, y (2 -4u)ufp(y) and

x = y + 4u ufp(y).

Writing y = (1 + 2ku)ufp(y) with k a nonnegative integer, we deduce that Assume now that p = 2. We have u = 1/4 and, assuming with no loss of generality that ufp(x) = 1, we see that x ∈ {1, 3/2} and that y is either ufp(y) or 3/2 • ufp(y). This yields four possibilities for t = x/y, all leading to E 1 (t) = E 2 (t) = 0 except for x = 1 and y = 3/2 • ufp(y). In this case, the constraint 1 < t < 2 implies further y = 3/4 = 1 -u. It follows that t = 1/(1 -u), from which we deduce fl(t) = 1 + 2u.

t = 1 + 4u 1 + 2ku , so t < 1 + 3u is equivalent to k > 2 p-1 /3, that is, k (2 p-1 + 1)/3
The announced bounds thus hold also in the case β = p = 2, and since 1 and 1 -u are in F, they are attained for (x, y) = (1, 1 -u).

3.4. Square root. Finally, we show how to refine further the bounds E 1 (t) u/(1 + u) and E 2 (t) u in the special case where t = √ x for some positive floating-point number x, thereby establishing the optimal bounds in the last row of Table 1. This result is independent of any specific property of the base and the precision, and holds for any tie-breaking strategy.

Theorem 3.4. Let β, p 2 and let x ∈ F be positive. Then

E 1 ( √ x) 1 - 1 √ 1 + 2u and E 2 ( √ x) √ 1 + 2u -1,
and these bounds are attained only for x = (1 + 2u)β 2e with e ∈ Z. The theorem below shows how to bound the sum of the |e i | and, therefore, | s -s| as well. This bound is slightly sharper than the one given in [10, Proposition 3.1] and can be established in the same way, using u/(1+u) instead of u to bound the relative rounding error committed by each floating-point addition. (For completeness a detailed proof is presented in Appendix B; note that as in [START_REF] Jeannerod | Improved error bounds for inner products in floating-point arithmetic[END_REF] this bound holds even if underflow occurs.) Theorem 4.1. For x 1 , . . . , x n ∈ F, any order of evaluation of the sum s = n i=1 x i produces an approximation s such that the rounding errors e 1 , . . . , e n-1 satisfy

Proof. Let t = √ x. Writing x = µβ 2e with e ∈ Z and µ ∈ F ∩ [1, β 2 ), we see that t = √ µ β e with µ ∈ {1, 1 + 2u, 1 + 4u, . . .}. If µ = 1 then E 1 (t) = E 2 (t) = 0,
checked that ϕ < 1 -1/ √ 1 + 2u for u 1/2. Furthermore, using √ 1 + 4u > 1 + u gives fl(t) (1 + 2u)β e and then E 2 (t) u/(1 + 2u) < √ 1 + 2u -1.
| s -s| n-1 i=1 |e i | σ n-1 n i=1 |x i |,
σ n := nu 1 + u .

2 For example, for n = 4 possible evaluation orders include ((x 1 + x 2 ) + x 3 ) + x 4 and ((x 4 +

x 3 ) + x 2 ) + x 1 and (x 1 + x 2 ) + (x 3 + x 4 ).

A direct consequence of this result is a sharper and simpler bound for the following compensated summation scheme (see [START_REF] Ogita | Accurate sum and dot product[END_REF] and the references therein):

s comp = fl( s + e),
e := a floating-point evaluation of e 1 + • • • + e n-1 .

Since each e i belongs to F and can be computed exactly-using for example Knuth's TwoSum algorithm [12, p. 236], we can apply Theorem 4.1 twice and, writing e = n-1 i=1 e i , we deduce that

(4.2) | e -e| σ n-1 σ n-2 n i=1 |x i |.
Since s = s + e, we have also

| s comp -s| |fl( s + e) -( s + e)| + | e -e| u 1 + u | s + e| + | e -e| u 1 + u |s| + 1 + u 1 + u | e -e|. (4.3)
Then, combining (4.2) and (4.3) and using the fact that (1

+ u 1+u )( u 1+u ) 2 u 2 1+u 2 we arrive at (4.4) | s comp -s| u 1 + u |s| + (n -1)(n -2) u 2 1 + u 2 n i=1 |x i |.
The bound in (4.4) holds without any restriction on n and regardless of the orderings used for adding the x i and adding the e i . Furthermore, it is slightly sharper than the bound u|s| + (n -1) [START_REF] Ogita | Accurate sum and dot product[END_REF]Proposition 4.5] in the special case of recursive compensated summation. 4.2. Sums of real numbers. We now turn to the case where x 1 , . . . , x n are in R instead of F. An approximation s ∈ F to s = x 1 + • • • + x n ∈ R is obtained in two steps, by first rounding each x i into fl(x i ) and then evaluating fl(x 1 ) + • • • + fl(x n ) as above. A typical example is the computation of inner products, where each x i is the exact product of two given floating-point numbers.

2 u 2 (1-(n-1)u) 2 n i=1 |x i | given in
Writing d i = x i -fl(x i ) for the errors due to rounding the data and, as before, e i for the errors due to the n -1 additions, we deduce that the exact and computed sums are now related as

(4.5) s = d 1 + • • • + d n + e 1 + • • • + e n-1 + s.
|d i | + n-1 i=1 |e i | ζ n n i=1 |x i |, ζ n := (1 + 2u)nu -u 2 (1 + u) 2 < nu.
Proof. The lower bound follows from (4.5). To establish the upper bound, let v = u/(1 + u). Theorem 4.1 gives

i<n |e i | (n -1)v i n |fl(x i )| and, on the other hand, (1.2) implies that |d i | v|x i | and |fl(x i )| (1 + v)|x i |. Hence i n |d i | + i<n |e i | (v + (n -1)v(1 + v)) i n |x i |,
and it is easily checked that v +(n-1)v(1+v) simplifies to ((1+2u)nu-u 2 )/(1+u) 2 , which is less than nu.

Thus, the theorem above gives in particular the bound

s - n i=1 x i ζ n n i=1 |x i |.
This bound has a slightly smaller constant than the one given in [10, Proposition 4.1] and, perhaps more importantly, its proof is significantly shorter and avoids a tedious induction and ufp-based case distinctions. Furthermore, the applications mentioned in [START_REF] Jeannerod | Improved error bounds for inner products in floating-point arithmetic[END_REF] obviously benefit directly from this new bound: for inner products, matrix-vector products, and matrix-matrix products, the constants nu obtained in [

- nu 1 + u θ n 1 + u 1 + u n -1.
Although the upper bound in (5.2) still has O(u 2 ) terms in general, it is bounded by nu as long as n 3. Consequently, by just systematically using E 1 (t) u/(1 + u) instead of E 1 (t) u, we can replace γ n = nu + O(u 2 ) by nu in every error analysis where θ n appears with n 3.

For example, when evaluating ab + cd in the usual way as r = fl(fl(ab) + fl(cd)), we have r = (ab(1 Similar examples include the evaluation of small arithmetic expressions like the product x 1 x 2 x 3 x 4 (using any parenthesization) or the sums ((x 1 +x 2 )+x 3 )+x 4 and ((x 1 +x 2 )+(x 3 +x 4 ))+((x 5 +x 6 )+(x 7 +x 8 )) (using these specific parenthesizations); in each case the forward error bound classically involves γ 3 , which we now replace by 3u.

+ δ 1 ) + cd(1 + δ 2 ))(1 + δ 3 ) with |δ i | u/(1 + u). Hence r = ab(1 + θ 2 ) + cd(1 + θ 2 ), |θ 2 |,

Example 2:

Leading principal minors of a tridiagonal matrix. Consider the tridiagonal matrix

A =         d 1 e 1 c
c n d n         ∈ F n×n ,
and let µ 1 , µ 2 , . . . , µ n be the sequence of its n leading principal minors. Writing µ -1 = 0 and µ 0 = 1, those minors are thus defined by the linear recurrence

µ k = d k µ k-1 -c k e k-1 µ k-2 , 1 k n.
Using the usual bound E 1 (t) u and barring underflow and overflow, Wilkinson shows in [19, §3] that the evaluation of this recurrence produces floating-point numbers µ 1 , . . . , µ n such that

µ k = d k (1 + k ) µ k-1 -c k (1 + k )e k-1 (1 + k ) µ k-2 , where (1 -u) 2 -1 k (1 + u) 2 -1 and (1 -u) 3/2 -1 k , k (1 + u) 3/2 -1.
In other words, the computed µ k are the leading principal minors of a nearby tridiagonal matrix

A + ∆A = [a ij (1 + δ ij )] that satisfies (5.3) -2u < δ ii 2u + u 2 and -3 2 u < δ ij 3 2 u + O(u 2 ) if i = j.
Notice that the terms u 2 and O(u 2 ) come exclusively from the upper bounds on k , k , k . By using the refined bound E 1 (t) u/(1 + u) from (1.2) instead of just E 1 (t) u, these upper bounds are straightforwardly improved to

k (1 + u 1+u ) 2 -1 < 2u and k , k (1 + u 1+u ) 3/2 -1 < 3 2 u.
Consequently, Wilkinson's bounds in (5.3) can be replaced by the following more concise and slightly sharper ones:

|δ ii | < 2u and |δ ij | < 3 2 u if i = j. 5.3. Example 3: Euclidean norm of an n-dimensional vector. Given a vec- tor [x 1 , . . . , x n ] T ∈ F n , let its norm r = x 2 1 + • • • + x 2 n
be evaluated in floating point in the usual way: form the squares fl(x 2 i ), sum them up in any order into s, and return r = fl √ s . By applying the usual bound E 1 (t) u, all we can say is s = (

n i=1 x 2 i )(1 + θ n ) with θ n as in (5.1), and r = √ s (1 + δ) with |δ| u. Consequently, r = r(1 + ), where = √ 1 + θ n • (1 + δ) -1 satisfies (1 -u) n/2+1 -1 (1 + u) n/2+1 -1.
Although the lower bound has absolute value at most (n/2+1)u-see for example [4, p. 42], the upper bound is strictly larger than this, so that (5.4)

-(n/2 + 1)u (n/2 + 1)u + O(u 2 ).
To avoid the O(u 2 ) term above, we can use the refined bound E 1 (t) u/(1 + u), which says |δ| u/(1 + u), together with the improved bound for inner products from [START_REF] Jeannerod | Improved error bounds for inner products in floating-point arithmetic[END_REF], which says |θ n | nu. Indeed, from these two bounds we deduce that is upper bounded by √ 1 + nu • (1 + u/(1 + u)) -1, and the latter quantity is easily checked to be at most (n/2 + 1)u. Thus, recalling the lower bound in (5.4), we conclude that (5.5) | | (n/2 + 1)u.

In particular, evaluating the hypotenuse x 2 1 + x 2 2 in floating-point produces a relative error of at most 2u; this improves over the classical bound 2u + O(u 2 ), stated for example in [7, p. 225].

Of course, the bound in (5.5) also applies when scaling by integer powers of the base is introduced to avoid underflow and overflow. 5.4. Example 4: Cholesky factorization. We consider A ∈ F n×n symmetric and its triangularization in floating-point arithmetic using the classical Cholesky algorithm. If the algorithm runs to completion, then by using the bounds E i (t) u, i = 1, 2, the traditional rounding error analysis concludes that the computed factor R satisfies R T R = A + ∆A with |∆A| γ n+1 | R T || R|; see for example [START_REF] Higham | Accuracy and Stability of Numerical Algorithms[END_REF]Theorem 10.3]. Here γ n+1 = (n+1)u 1-(n+1)u has the form (n + 1)u + O(u 2 ) and requires n + 1 < u -1 . It was shown in [START_REF] Rump | Improved backward error bounds for LU and Cholesky factorizations[END_REF] that both the quadratic term in u and the restriction on n can be removed, resulting in the improved backward error bound |∆A| (n + 1)u| R T || R|.

In the proof of [START_REF] Rump | Improved backward error bounds for LU and Cholesky factorizations[END_REF]Theorem 4.4], one of the ingredients used to suppress the O(u 2 ) term is the following property: In [START_REF] Rump | Improved backward error bounds for LU and Cholesky factorizations[END_REF] it is shown that this property may not hold if only the bound E 2 (t) u is assumed, and that in this case all we can say is -(2u + u 2 )b 2 b 2 -a 2ub 2 . Furthermore, a proof of (5.6) is given, which is about 10 lines long and based on a ufp-based case analysis; see [15, p. 692].

Instead, our optimal bound on E 2 for square root provides a direct proof: Theorem 3. Various approximations z = R + i I to z can be obtained, depending on how R = ac -bd and I = ad + bc are evaluated in floating-point. It was shown in [START_REF] Brent | Error bounds on complex floating-point multiplication[END_REF] that the conventional way, which uses 4 multiplications and 2 additions, gives z = z(1 + ) with ∈ C such that | | < √ 5u, and that the constant √ 5 is, at least in base 2, best possible. Assume now that an FMA is available, so that we compute, say, R = fl(ac -fl(bd)) and I = fl(ad + fl(bc)).

For this algorithm and its variants 3 it was shown in [START_REF] Jeannerod | Error bounds on complex floating-point multiplication with an FMA[END_REF] that the bound √ 5u can be reduced further to 2u, and that the latter is essentially optimal. The fact that 2u is an upper bound is established in [START_REF] Jeannerod | Error bounds on complex floating-point multiplication with an FMA[END_REF]Theorem 3.1] with a rather long proof. As we shall see in the paragraph below, a much more direct proof follows from simply applying the refined bound E 1 (t) u/(1 + u) in a systematic way.

Denoting by δ 1 , . . . , δ 4 the four rounding errors involved, we have

4. Application to summation 4 . 1 .

 41 Sums of floating-point numbers. Consider first the evaluation of the sum of n floating-point numbers. Here x 1 , . . . , x n ∈ F are given and we assume that an approximation s ∈ F to the exact sums = x 1 + • • • + x nis produced after n-1 floating-point additions, using any evaluation order.2 Each of these additions takes a pair of floating-point numbers, say (a, b) ∈ F 2 , and returns fl(a + b), thus committing the local error e := a + b -fl(a + b). When evaluating the sum as above, n -1 such errors can occur and, denoting their set as {e 1 , . . . , e n-1 }, it is easy to see that (4.1) s = e 1 + • • • + e n-1 + s; see for example [5, p. 81].

By combining ( 1 . 2 )Theorem 4 . 2 .

 1242 and Theorem 4.1 we obtain almost immediately the following bound on the sum of the |d i | and the |e i |. For x 1 , . . . , x n ∈ R, any order of evaluation of the sum n i=1 fl(x i ) produces an approximation s to the sum s = n i=1 x i such that the rounding errors d 1 , . . . , d n and e 1 , . . . , e n-1 satisfy | s -s| n i=1

(5. 6 )

 6 a ∈ F 0 and b = fl √ a ⇒ |b 2 -a| 2ub 2 .

5 . 5 .

 55 4 gives b(1 + δ) = √ a with |δ| √ 1 + 2u -1; hence |b 2 -a| = b 2 |2δ + δ 2 | and |2δ + δ 2 | (2 + |δ|)|δ| ( √ 1 + 2u + 1)( √ 1 + 2u -1) = 2u,from which (5.6) follows immediately. Example 5: Complex multiplication with an FMA. Given a, b, c, d ∈ F, consider the complex product z = (a + ib)(c + id).

R 2 λ 2

 22 = (ac -bd(1 + δ 1 ))(1 + δ 2 ) = R + Rδ 2 -bdδ 1 (1 + δ 2 )and, similarly,I = I + Iδ 4 + bcδ 3 (1 + δ 4 ). Now let λ, µ ∈ R 0 be such that |δ 2 |, |δ 4 | λ and |δ 1 (1 + δ 2 )|, |δ 3 (1 + δ 4 )| µ.This implies that |R -R| λ|R| + µ|bd| and |I -I| λ|I| + µ|bc|, from which we deduce|z -z| 2 = (R -R) 2 + (I -I) |z| 2 + 2λµA + µ 2 B, (5.7) where A = |R||bd| + |I||bc| and B = (bd) 2 + (bc) 2 . It turns out that (5.8) A, B |z| 2 . For B, this bound simply follows from the equality |z| 2 = (ac) 2 +(bd) 2 +(ad) 2 +(bc) 2 . For A, define π = abcd and notice that A = |π -(bd) 2 | + |π + (bc) 2 | is equal to either B or ±(2π + (bc) 2 -(bd) 2 ); furthermore, in the latter case we have

Table 1 .

 1 Optimal relative error bounds for various inputs t.

	t	bound on E 1 (t)	bound on E 2 (t)
	real number	u 1+u	u
	x ± y	u 1+u	u
	xy	u 1+u

  10, Theorem 4.2 and p. 343] can all be replaced by ζ n . 5. Other application examples 5.1. Example 1: Small arithmetic expressions. Rounding error analyses as those done in [5] typically involve bounds on |θ n |, where θ n is an expression of the form θ n = n i=1 (1 + δ i ) -1 with δ i a relative error term associated with a single floating-point operation. Using the classical bound |δ i | u it is easily checked that for all n,

	(5.1)	-nu θ n (1 + u) n -1.
	Note that only the upper bound has the form nu + O(u 2 ), that is, contains terms
	nonlinear in u. From (5.1) it follows that
		|θ n | (1 + u) n -1
	and, assuming nu < 1, this bound itself is usually bounded above by the classical
	fraction γ n = nu/(1 -nu).
	Using the refined bound E 1 (t) u/(1 + u) from (1.2), we can replace |δ i | u
	by |δ i | u/(1 + u), which immediately leads to the refined enclosure
	(5.2)

  |θ 2 | 2u, so the usual γ 2 is indeed replaced by 2u. Note that once we have replaced E 1 (t) u by E 1 (t) u/(1+u), we obtain that term 2u immediately, without having to resort to a sophisticated ufp-based argument as the one introduced in [1, pp. 1470-1471].

  2 d 2 e 2

	. . .	. . .	. . .
		. . .	. . . e n-1

A 2|π| + (bc) 2 -(bd) 2 min (ac) 2 + (bd) 2 , (ad) 2 + (bc) 2 + max (bc) 2 , (bd) 2 |z| 2 . Thus, combining (5.7) and (5.8), |z -z| (λ + µ)|z|. Since the refined bound E 1 (t) u/(1 + u) implies |δ i | u/(1 + u) for all i, we can take λ = u/(1 + u) and µ = u/(1 + u) • (1 + u/(1 + u)), which are both less than u. Hence, barring underflow and overflow and since z = 0 implies z = 0, we conclude that

Note that 2u+3u 2 (1+u) 2 has the form 2u -u 2 + O(u 4 ) as u → 0. Thus, our approach not only yields a shorter and more direct proof of the bound 2u of [START_REF] Jeannerod | Error bounds on complex floating-point multiplication with an FMA[END_REF], but it also improves on that bound.

Appendix A. Proof that p as in (3.4) is not a power of two If j ∈ {5, 6, 7}, then p ∈ {144, 175, 206} and is not a power of two. Assume now that j 8. Writing d = 4m + i for integers m, i with 0 i 3, we have

If i = 0, this implies 2 m+1/8 k 2 m+7/8 and then 2 m+1/8 -4m + 10 p 2 m+7/8 -4m + 12.

3 There are three other ways to insert the innermost rounding fl, all giving the same error as the one developed here.

Since the assumption j 8 implies k 2 8 and thus m 8, it follows that 2 m < p < 2 m+1 . Consequently, p cannot be a power of two when i = 0. On the other hand, when i = 0, we see that p = 32j -4m + 13 must be odd, and thus cannot be a power of two neither. The lower bound follows from (4.1) and the triangle inequality. For the upper bound, the proof is by induction on n, the case n = 1 being trivial (since then there is no rounding error at all). For n 2, we assume that the result is true up to n-1, and we fix one evaluation order in dimension n. The approximation s obtained with this order has the form s = fl( s 1 + s 2 ), where s j is the result of a floating-point evaluation of s j = i∈Ij x i for j = 1, 2 and with {I 1 , I 2 } a partition of the set I = {1, 2, . . . , n}. For j = 1, 2 let n j be the cardinality of I j and let e (1) j , . . . , e (nj -1) j be the rounding errors committed when evaluating s j , so that s j = i<nj e (i) j + s j . Consequently,

Since 1 n j < n, the inductive assumption leads to

where

To do so, we note that (1.2) and [10, Lemma 2.2] imply that

and we consider the following three cases. Assume first that s 2 u/(1 + u) • s 1 . Then s 2 s 1 and, using |δ| | s 2 |, we obtain and | s j -s j | (n j -1)u/(1 + u) • s j (n j -1) s k for (j, k) ∈ {(1, 2), (2, 1)}. Hence (B.1) follows in this third case as well, thus completing the proof of Theorem 4.1.