João Paulo Esper
email: joaopauloesper@dcc.ufmg.br

Nadjib Achir
email: nadjib.achir@univ-paris13.fr

Vieira Kleber
email: kleber@inf.ufg.br

Cardoso

Jussara M Almeida
email: jussara@dcc.ufmg.br

Impact of User Privacy and Mobility on Edge Offloading

Keywords: Offloading, MEC, mobility, privacy

Offloading high-demanding applications to the edge provides better quality of experience (QoE) for users with limited hardware devices. However, to maintain a competitive QoE, infrastructure, and service providers must adapt to users' different mobility patterns, which can be challenging, especially for location-based services (LBS). Another issue that needs to be tackled is the increasing demand for user privacy protection. With less (accurate) information regarding user location, preferences, and usage patterns, forecasting the performance of offloading mechanisms becomes even more challenging. This work discusses the impacts of users' privacy and mobility when offloading to the edge. Different privacy and mobility scenarios are simulated and discussed to shed light on the trade-offs (e.g., privacy protection at the cost of increased latency) among privacy protection, mobility, and offloading performance.

Introduction

Mobile devices have undergone a significant transformation from small devices with limited capacity to mobile mini-computers, leading to exponential growth in the mobile application markets. However, with this growth comes a sharp increase in application needs in terms of computational resources from applications such as virtual Draft reality (VR), augmented reality (AR), and interactive games [START_REF] Akrem Addad | Fast service migration in 5G trends and scenarios[END_REF], which even our modern mobile terminals cannot well fulfill.

To tackle this issue, edge computing was proposed as a technology in which computational resources are moved to the Edge of the network to reduce latency and guarantee the quality of service [2]. Thus, users may run their applications on the Edge using offloading techniques. This combination provides the user equipment (UEs) with reduced CPU usage, extended battery life, support for more robust and sophisticated applications, and potentially unlimited storage [START_REF] Zhan | Mobility-aware multi-user offloading optimization for mobile edge computing[END_REF].

One challenge that offloading algorithms face is related to user mobility [START_REF] Yang | Efficient mobility-aware task offloading for vehicular edge computing networks[END_REF]. Users who run their applications on the Edge can move freely in the city, which may significantly affect some applications. Thus, adapting to the users' mobility patterns becomes a challenge as Multi-access Edge Computing (MEC) providers want to keep users' Quality of Experience (QoE) while also dealing with the stress of mobility on their infrastructure through complex operations, e.g., task reallocation. Another issue that operators and service providers have recently faced is that users are becoming increasingly aware and concerned about their privacy. As such, governments in various parts of the world responded to this concern with data protection and privacy regulations, e.g., RGPD 1 in Europe and LGPD2 in Brazil. For example, as illustrated by Figure 1, Android 12, released in 2021, changed how user location is accessed, and now users can choose between providing their precise locations or approximate ones.

Privacy concern is an issue for operators and service providers because they need to keep users' privacy and adapt and improve their techniques, e.g., offloading techniques, to maintain competitive performance. In most cases, the more accurate the information you have about the user (e.g., his location), the easier it becomes to predict and anticipate user demand. Yet, most prior studies have evaluated Edge offloading without any consideration of location privacy, especially in complex scenarios composed of multiple applications, each one with distinct requirements, as well as heterogeneous mobility patterns (reflecting, for instance, different mobility types), while analyzing how each of these factors (and combinations of them) may affect the offloading performance.

Our goal is to fill this gap by investigating the impact of user mobility and privacy when offloading to the Edge in multi-application and multi-mobility scenarios. To that end, we employ a combination of state-of-the-art techniques/tools related to mobility and privacy to simulate a large set of scenarios with different user privacy and mobility patterns. As such, our goal is not to propose a new privacy or security technique but rather to offer insights (e.g., how slow mobility types can suffer more with privacy than fast ones) into the trade-offs between user privacy, mobility, and computational offloading performance.

The rest of the paper is structured as follows. Section 2 presents related work. Section 3 describes the system model and problem description. Sections 4 and 5 discuss our evaluation methodology and main results, respectively, while Section 6 offers conclusions and directions for future work.

Related work

Prior work mostly related to our effort tackles (combinations of) aspects related to user privacy, mobility, multiapplication scenarios, edge computing, and offloading. However, many of them only considered a few of these aspects. For example, in [START_REF] He | Privacy-aware offloading in mobile-edge computing[END_REF], authors discussed the privacy issues of task offloading with MEC from two perspectives, location privacy, and usage privacy. The authors proposed a Markov decision process to improve latency and energy consumption while keeping pre-specified levels of privacy, but no mobility analysis was offered. Authors in [START_REF] Sun | Reducing offloading latency for digital twin edge networks in 6G[END_REF] focused on minimizing offloading latency considering user mobility and movement for AR users but did not consider privacy. In turn, authors in [START_REF] Wei | UAV-assisted privacy-preserving online computation offloading for internet of things[END_REF] focused on task offloading in a scenario of unmanned aerial vehicles with limited energy and computing capacities. The paper focused on privacy but from a computation offloading preference leakage perspective, not focusing on user location privacy.

In contrast, two recent studies have jointly explored most of those aspects. In [START_REF] Peng | Mobility and Privacy-Aware Offloading of AR Applications for Healthcare Cyber-Physical Systems in Edge Computing[END_REF], the authors proposed a mobility and privacy-aware offloading meta-heuristic method for a particular scenario, namely, AR applications that deal with patients' private information in healthcare systems. Instead, we here consider scenarios where requests from diverse applications compete to be able to offload their requests. In [START_REF] Pang | Towards Online Privacypreserving Computation Offloading in Mobile Edge Computing[END_REF], the authors focused on the privacy leakage issue of MEC offloading, assuming an honest-but-curious server as we do in this paper. They proposed a computational offloading mechanism that provides user privacy while minimizing the total computation cost. However, their work considered homogeneous user mobility patterns, whereas we explored different mobility classes, which, as will be discussed, significantly impact the results.

System model and problem description

Let us consider a MEC environment composed of a set B = {1, 2, ..., B} of base stations (BSs) and a set M = {1, 2, ..., M} of MEC Hosts (MHs), as illustrated in Figure 2. Any BS can reach and offload user applications to any MH of choice. Each BS i (MH j) has a throughput capacity of T BS i (T MH j ). We consider a set U = {1, 2, ..., U} of users, each one modeled by a mobility type, an application, and a privacy level. The user mobility type can be car passenger, bus passenger, or pedestrian. The application can be video streaming, AR, or VR. Finally, the privacy level can be none, medium, or high. Each application has particular requirements in terms of network resources, which are expressed as: • A t : the throughput demand (i.e., demanded traffic volume), measured in megabits per second (Mbps).

• A l : the latency demand (i.e., maximum accepted latency), measured in milliseconds (ms).

The throughput demand is met if there are enough network resources available at the selected MH j (i.e., T MH j ≥ A t ) and if the throughput between the UE and the BS the user is associated to is greater or equal than the throughput demand. The throughput between UE-BS is computed using Shannon's capacity formula [START_REF] Stallings | Data and computer communications[END_REF]. If the total throughput from the UEs connected to BS i exceeds T BS i , BS i's capacity is distributed among them following the proportional fairness method [START_REF] Kim | A proportional fair scheduling for multicarrier transmission systems[END_REF].

The latency demand is met if the latency between the BS the user is associated with and the MH selected to handle his request is less than or equal to the latency demand. The latency between BS-MH in this work is calculated based on the distance between the BS and the MH.

This work assumes that the UE is always associated with the closest (Euclidean distance) BS. Once the UE is associated, it requests the network provider to offload an application. The network provider will then report the UE's position to the MEC provider, which, in turn, will assign the closest MH to the BS the UE is associated with to handle the user's request, i.e., offload the application. Finally, if the requirements of the user's application are met, it is offloaded to the MEC system, consuming A t resources from the MH j it was allocated to.

Figure 3 illustrates how we model privacy in our system. We assume the existence of two infrastructure entities: i) the network provider; responsible for the BSs, communication, routing, etc., and ii) the MEC provider; responsible for the MH computational resources. We aim to protect user location from the MEC provider's perspective, as trying to mask (or fake) the user's real location from the network provider is a different challenge since the UE is associated with a BS3 .

MH2

MH1

Closest MH

Geo-indistinguishability area

Closest MH In Figure 3, we represent two different MH selections, a non-private selection and a private selection. A nonprivate selection, illustrated by the pedestrian in the center of the circle, occurs when the user is not concerned with his location privacy (privacy level set to none). In this case, the network provider will report the user's real location to the MEC provider, and the MEC provider will assign MH1, which corresponds to the closest MH to the BS to which the user is connected. MH1 will then handle the user's request.

Real location

Fake location

Non

A private selection, in turn, occurs when the user is concerned about his location privacy, which corresponds to a privacy level set to medium or high. In this case, the network provider knows the user's real location. Yet, it will apply geo-indistinguishability [START_REF] Miguel E Andrés | Geoindistinguishability: Differential privacy for location-based systems[END_REF], a state-of-the-art technique based on differential privacy, to generate a fake location, represented by the pedestrian near the circle's edge (see further discussion below). The network provider reports to the MEC provider the user's fake location (not the real one). The MEC provider, in turn, will assume the user is connected to the BS at the bottom of the figure and will assign MH2 to it, as it is the closest MH to that particular BS. MH2 will then handle the user's request. Hence, the user will gain privacy but he may lose performance as his application may no longer be offloaded to the MH that is closest to the BS he is actually connected to. This may affect application latency, resulting in QoE degradation or even failing the application demands, leading to a denied request.

To check if the application latency demand is met, the MEC provider asks the network provider to measure the latency between the selected MH and the BS to which the user is connected. The application is offloaded if the obtained latency is less than or equal to the application demand. We note that the MEC provider could ask the network provider to measure the latency between the selected MH to all BSs to gain more information about the user's real location. Yet, it would be cost-inefficient to do that for every user request in a large-scale environment. Also, to efficiently guarantee user location privacy, we assume an honest-but-curious adversary [START_REF] Pang | Towards Online Privacypreserving Computation Offloading in Mobile Edge Computing[END_REF][START_REF] Paverd | Modelling and automatically analysing privacy properties for honest-but-curious adversaries[END_REF], meaning Draft

ε = ∞, 0.1, 0.01
that the MEC provider will not deviate from the defined protocol, even though it attempts to learn all possible information from legitimately received requests.

As mentioned, we here use geo-indistinguishability to provide location privacy for the user by producing a new (fake) location. Figure 4 illustrates how this method works. Consider a tourist in Toronto, visiting the Royal Ontario Museum, who intends to offload his application or do any kind of LBS request. The tourist, concerned with his privacy, does not wish to share his precise location (represented by a red point). Instead, he will share an approximate (fake) location. Geo-indistinguishability works by defining a circle centered around the user's real location and uniformly selecting a new/fake location inside this circle. The circle's radius is computed based on parameter ε. Smaller values of ε result in greater circle's radius. The new location selection is uniform across the circle. Thus a bigger circle around the user will cover more locations, lowering the probability that real and fake locations are close to each other. Thus, greater privacy levels are achieved by using smaller ε values as these lead to greater noise added to fake the user's real position.

Given that the relationship between ε and privacy is inversely proportional, ε = ∞ is a baseline in this mechanism, and it represents the user's real position, i.e., if ε = ∞, then privacy is non-existent. In Figure 4, five different ε values are presented, each one next to the circle it generated, such that ε ∞ > ε 4 > ε 3 > ε 2 > ε 1 . As illustrated, with a larger value of ε, e.g., ε 4 , geo-indistinguishability has fewer locations to assign a new (fake) position for the tourist, mainly outside of the museum or in nearby streets. In contrast, a smaller value of ε, e.g., ε 3 , can generate fake positions that ε 4 could not, such as the University of Toronto or the Toronto Public Library.

Evaluation methodology

This section defines our evaluation methodology by introducing the main parameters used to build our evaluation scenarios. Recall that our goal is to tackle the question: What are the impacts of user privacy and mobility when offloading to the edge? Thus, our parameters, summarized in Tables 1 and2, relate to mobility, privacy, and (edge) infrastructure and computational resources.

We simulated different user mobility patterns by considering three mobility types: car passengers, bus passengers, and pedestrians. To that end, we used SUMO (Simulation of Urban MObility) 4 , a widely used mobility simulator. We simulated 30 different runs with SUMO following the Manhattan Mobility Model (2 km × 2 km). We used the population density reported in [START_REF] Zhou | On the spatial distribution of base stations and its relation to the traffic density in cellular networks[END_REF], i.e., 312.5 users/km 2 , resulting in a total of 1,250 users, which were distributed into the three mobility types as follows: 400 car passengers, 400 bus passengers, and 450 pedestrians. We assume that each car has one passenger and each bus has 10 passengers, generating a total of 440 vehicles in the area (400 cars and 40 buses).

To quantify and position BSs and MHs in the simulated area, we used Homogeneous Poisson point processes (HPPP), as done in [START_REF] Zhou | On the spatial distribution of base stations and its relation to the traffic density in cellular networks[END_REF]. Specifically, we set the HPPP intensity parameter λ to 118.75, as reported for 'Urban Area 1' in [START_REF] Zhou | On the spatial distribution of base stations and its relation to the traffic density in cellular networks[END_REF], leading to 475 BSs, and used λ =23.75 to generate and position 95 MHs in the simulated area. We assumed that each BS i has a capacity T BS i of 10 Gbps, as reported by 3GPP [START_REF] Gpp | Study on scenarios and requirements for next generation access technologies[END_REF], and each MH j has a capacity of T MH j of 10.41 Gbps [START_REF] Spinelli | Toward enabled industrial verticals in 5G: A survey on MECbased approaches to provisioning and flexibility[END_REF]. We defined three user privacy levels by varying the ε parameter used by the geo-indistinguishability method. As discussed, the smaller the value of ε, the more private the user's (real) position becomes. The first level, referred to as none, corresponds to ε = ∞, the case when the user chooses not to have location privacy (user's real and fake positions are the same). It is used here as a baseline for comparison. The other two levels, i.e., medium and high, are defined by setting ε = 0.1 and ε = 0.01 respectively, following a prior study on location privacy in the edge [START_REF] Qiao | An effective data privacy protection algorithm based on differential privacy in edge computing[END_REF].

To make our evaluation more realistic, we also considered the throughput and latency requirements of three different types of applications: video streaming, augmented reality (AR), and virtual reality (VR), as presented in Table 2. The video streaming and AR requirements were obtained from [START_REF] Spinelli | Toward enabled industrial verticals in 5G: A survey on MECbased approaches to provisioning and flexibility[END_REF], whereas those for VR were obtained from [START_REF] Lai | Furion: Engineering high-quality immersive virtual reality on today's mobile devices[END_REF], both focusing on 5G scenarios. Following Cisco6 and Ericsson7 forecasts for network traffic in the following years, we defined that 70% of the users are consuming a video streaming application. We distributed the rest of the traffic (30%) evenly between AR and VR. We assume that the VR application does not fit the pedestrian mobility type since they cannot be fully aware of their surroundings if they use a VR headset while walking. Thus, we set that the pedestrians can only use a video streaming or AR application, while other mobility types can use any of the three applications.

We conducted several experiments covering three user mobility patterns, three application types, and three privacy protection scenarios. In short, given an input privacy level (ε = ∞, 0.1 or 0.01), we ran 30 simulations (by varying the seed) with user population (mobility patterns and applications) as described above, producing a total of 90 different experiments. As discussed next, our results present very narrow 95% confidence intervals, suggesting high accuracy.

Evaluation results

We now discuss our results of the impact of privacy, mobility and application types on the offloading performance.

Impact of privacy level

We start by evaluating the impact of the privacy level, captured by the value of ε, on the acceptance of requests. We do so by comparing the outcome of each user request -offload was successful or failed -for each privacy level (ε equal to ∞, 0.1, and 0.01). Recall that an offload request is successful whenever there is enough resource at the selected MH and the user application's bandwidth and latency requirements are met. Considering the totality of user requests issued during a simulation run, we classify them into one of the three scenarios: Always offloaded, Privacy dependent, and Never offloaded. The former corresponds to requests that were successful in all runs, whereas the latter relates to requests that failed in all runs, regardless of the value of ε. Both categories relate to requests that were not impacted by the particular privacy level adopted. Requests whose outcome varied depending on the value of ε used fall into the privacy dependent category. Table 3 presents the average fraction of user requests falling in each category, along with 95% confidence intervals. As shown, most requests (around 56%, on average), were offloaded in all privacy levels. This means that, in all these cases, regardless of the privacy level chosen (∞, 0.1, or 0.01), the user was always able to successfully offload his desired application. We delve deeper into this result by breaking down these requests by application type. We note that over 98% of the requests for AR (the least bandwidth and latency demanding application) were offloaded in all privacy levels. In contrast, only around 47% of the video requests (the most demanding in terms of latency) and 31% of the VR requests (the most demanding in terms of bandwidth) were always offloaded regardless of the privacy level. Thus, as one might expect, privacy has less impact on offloading requests that impose lower requirements. Yet, we note that even though both application requirements and privacy needs could be successfully fulfilled for those requests, users still paid a price for privacy as the latency of these requests did increase for higher levels of protection (as discussed below).

In contrast, around 30% of the requests fell into the Privacy dependent category, implying that the success of the offload depended on the user's privacy level. The vast majority of those requests, or 28% of all requests, were accepted for privacy levels equal to none and medium failing only for privacy level equal to high. Thus, in total, a user was able to successfully offload his application while still maintaining a medium privacy protection in roughly 84% of the time (56% + 28% of all requests). A high privacy level, in turn, is more challenging as it more often leads to request being denied.

We note that around 14% of the requests were never offloaded, regardless of the privacy level (even for no privacy protection). We then zoom deeper into the reasons why users were not able to offload their applications in each of the privacy scenarios. Recall that the denial of an offload request may happen because8 : 1) the latency between the BS the UE is associated with and the selected MH is above the application's latency requirement (blue bars); 2) the throughput between the UE and the BS is not enough to meet the application's throughput requirement (green bars); 3) both latency and throughput requirements are not met (red bars).

As shown in Figure 5, for all privacy levels, the first reason -high latency between BS and MH -dominates all cases, often occurring for requests to offload video streaming, the most latency demanding application. Moreover, the fraction of requests denied due to this reason increases with privacy protection. This happens because smaller ε values imply in greater chance that the MEC operator selects an MH that is farther from the BS the UE is associated with (true and fake user locations far from each other), resulting in higher latency.

The other two reasons, in turn, occurred with much lower frequency, often for requests to offload the VR application (with the highest bandwidth demands). We note that the privacy level does not impact the fraction of requests denied due to lack of throughput between the UE and the BS (reason 2) since there is no privacy from the network operator's standpoint (i.e., user's BS is the same for all privacy levels). Yet, we do observe a small increase in the fraction of requests denied due to reason 3, i.e., both application requirements are not fulfilled, in the most private scenario (ε = 0.01). Such increase is mostly due to the longer latency that result from the higher Draft

Impact of mobility type

We now turn our attention to how privacy impact the MH selection for different mobility types. As detailed in Section 3, the MEC operator selects the MH closer to the BS he thinks the UE is associated with, which might be right or not. Figure 6 presents the fractions of MH selections that differ from the ideal one (closest to the true BS) for each mobility type.

Naturally, with no privacy protection (ε = ∞), the selected MH is always ideal. Yet, the fraction of selections resulting in different MHs increases with the privacy level for all three mobility types, reaching at least 60% for high privacy. Also, Figure 6 shows that the slowest mobility type (pedestrian) is more impacted by privacy than the other two types, reaching 70% of non-ideal MH selections for the high privacy level.

Prior work has analyzed the impact of mobile user's speed on offloading performance under privacy protection [START_REF] Pang | Towards Online Privacypreserving Computation Offloading in Mobile Edge Computing[END_REF], focusing on a single mobility type. Our result suggests that, in addition to speed, different user mobility patterns, notably where and how the user moves, may also impact offloading with privacy protection. Pedestrians move only on the sidewalks and crosswalks, while cars and buses move only on the streets. Also, car/bus flow is influenced by traffic jams and traffic lights, while pedestrians move more freely on the sidewalks, hardly ever facing traffic lights on crosswalks. Depending on BSs and MHs limitations, MEC selection may be impacted differently as spatial constraints (sidewalks, crosswalks or streets) of each mobility type can offer an advantage (or disadvantage) once privacy protection is applied.

Figure 7 shows the latency increase caused by the non-ideal MH selections for each privacy level and mobility type. As shown, car and bus passengers had similar results as they have similar mobility patterns. However, pedestrians again suffered more the impact of privacy, with an average latency increase near 220% for high privacy level. As argued in the previous section, even if the user is able to offload his application, the price of privacy protection comes in the form of increased latency which, as Figure 7

Impact of application type

Our last analysis focuses on the user requests that were successful (i.e., user could successfully offload his application) when the privacy level was set to none but not on both remaining levels, shedding light into how mobility and application of choice may impact users who could not achieve their desired privacy level. Figure 8 shows the fractions of those requests, computed over the total number of requests for each combination of mobility type and application type. As shown, for all mobility types, requests to the video streaming application, the most demanding in terms of latency, are the most affected by privacy protection. As already argued, the applications' latency requirement is more challenging to maintain than the bandwidth requirement, provided that MH capacity does not saturate. Moreover, once again we observe that pedestrians suffered more than car and bus passengers, emphasizing the importance of mobility patterns and how natural spatial constraints on mobility may yield different offloading performance. Finally, we make source code and all data used in our experiments (including ∼405 million user requests on different privacy and mobility scenarios) publicly available for the sake of reproducibility and fostering future research 9 .

Conclusions and future work

In this work, we analyzed the impacts of users' privacy and mobility when offloading to the edge. We carried out a large number of simulations based on multiple real-world scenarios, parameters, and applications, each with a specific user mobility model and privacy requirement scenario, in order to analyze the impacts that privacy and mobility can have. Additionally, we made publicly available code and data necessary for replicating our work. As future work, we plan to test different/adaptive privacy levels based on the UE's Quality of Service (QoS) and on the user's mobility pattern; analyze how different MH selection algorithms from the literature are affected by the privacy, and explore our findings in the design of novel MH selection algorithms that achieve competitive results while keeping predefined user privacy levels.

Figure 1 :

 1 Figure 1: Precise vs. approximate location on Android 12.Another issue that operators and service providers have recently faced is that users are becoming increasingly aware and concerned about their privacy. As such, governments in various parts of the world responded to this concern with data protection and privacy regulations, e.g., RGPD 1 in Europe and LGPD 2 in Brazil. For example, as illustrated by Figure1, Android 12, released in 2021, changed how user location is accessed, and now users can choose between providing their precise locations or approximate ones.Privacy concern is an issue for operators and service providers because they need to keep users' privacy and adapt and improve their techniques, e.g., offloading techniques, to maintain competitive performance. In most cases, the more accurate the information you have about the user (e.g., his location), the easier it becomes to predict and anticipate user demand. Yet, most prior studies have evaluated Edge offloading without any consideration of location privacy, especially in complex scenarios composed of multiple applications, each one with distinct requirements, as well as heterogeneous mobility patterns (reflecting, for instance, different mobility types), while analyzing how each of these factors (and combinations of them) may affect the offloading performance.Our goal is to fill this gap by investigating the impact of user mobility and privacy when offloading to the Edge in multi-application and multi-mobility scenarios. To that end, we employ a combination of state-of-the-art techniques/tools related to mobility and privacy to simulate a large set of scenarios with different user privacy and mobility patterns. As such, our goal is not to propose a new privacy or security technique but rather to offer insights (e.g., how slow mobility types can suffer more with privacy than fast ones) into the trade-offs between user privacy, mobility, and computational offloading performance.The rest of the paper is structured as follows. Section 2 presents related work. Section 3 describes the system model and problem description. Sections 4 and 5 discuss our evaluation methodology and main results, respectively, while Section 6 offers conclusions and directions for future work.

Figure 2 :

 2 Figure 2: System overview.

Figure 3 :

 3 Figure 3: Privacy overview.

Figure 4 :

 4 Figure 4: Geo-indistinguishability mechanism representation, inspired by [4].

Figure 5 :

 5 Figure 5: Reasons for request denials for various privacy levels.

Figure 6 :

 6 Figure 6: Impact of privacy and mobility on the MH selection.

Figure 7 :

 7 Figure 7: Impact of privacy and mobility on latency increase.

Figure 8 :

 8 Figure8: Fraction of requests that succeeded when the privacy level was none but not on both remaining levels.

Table 1 :

 1 Simulation parameters.

	Runs Area	Users Car	Bus	Pedes. BSs MHs BS capac-	MH ca-	Privacy
				pas.	pas.			ity	pacity	levels
	30	4 km 2 1250	400	400	450	475 95	10 Gbps	10.41
									Gbps

Table 2 :

 2 Applications parameters.

	Application Bandwidth	Latency req.	% of cars pas.	% of bus pas.	% of pedes. us-
		req.		using	using	ing
	Video	70 Mbps	10 ms	70%	70%	70%
	AR	100 Mbps	30 ms	15%	15%	30%
	VR	132 Mbps	14 ms	15%	15%	-
	a different seed. Each run lasts for 1 hour, with a temporal resolution of 1 second, and considers a squared area
	of 4 km 2

5

, each time with Draft

Table 3 :

 3 Impact of privacy on acceptance of requests: fraction of requests in each category and 95% confidence intervals.

		Always offloaded Privacy dependent Never offloaded
		56.37% ± 0.06	30.03% ± 0.07	13.58% ± 0.10
	20 40 60 80 100 % of requests	High latency between BS and selected MH Not enough bandwidth between UE and BS Both
	0	=	= 0.1	= 0.01

  shows, impacts pedestrian's mobility patterns the most.

	% of req. dependent on privacy level none	0 20 40 60 80 100	Car Video	Car AR	Car VR	Bus Video	Bus AR	Bus VR	Pedes. Video	AR Pedes.
						Draft

https://eur-lex.europa.eu/eli/reg/2016/679/oj

https://www.gov.br/cidadania/pt-br/acesso-a-informacao/lgpd

Even though there are works that consider the network and MEC provider being only one entity, this assumption is not in the scope of this work.

https://www.eclipse.org/sumo/

https://sumo.dlr.de/docs/Tutorials/Manhattan.html

https://www.cisco.com/c/en/us/solutions/collateral/executive-perspectives/annual-internet-report/white-paper-c11-741490.html

https://www.ericsson.com/en/mobility-report/reports/november-2019/mobile-traffic-by-application-category

We note that, for simulation purposes and given the limited area considered, all requests are always associated with a BS. Thus, request denials cannot occur due to the lack of coverage by nearby BS.

https://github.com/LABORA-INF-UFG/Offloading

Acknowledgements

The authors thank Mário S. Alvim for his contributions and insights regarding privacy protection. This work was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), by Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG), by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) and in by the CAPES-STIC-AMSUD 22-STIC-07 LINT project.


E Millour
email: millour@lmd.jussieu.fr

F Forget

A Spiga

Margaux Vals

V Zakharov

L Montabone

Franck Lefèvre

Franck Montmessin

Jean-Yves Chaufray

M A López-Valverde

J.-Y Chaufray

F González-Galindo

S R Lewis

P L Read

M.-C Desjean

F Cipriani

The Mars Climate Database (Version 5.3)

and research institutions in France or abroad, or from public or private research centers.

Introduction:

The Mars Climate Database (MCD) is a database of meteorological fields derived from General Circulation Model (GCM) numerical simulations of the Martian atmosphere and validated using available observational data. The MCD includes complementary post-processing schemes such as high spatial resolution interpolation of environmental data and means of reconstructing the variability thereof.

The GCM that is used to create the MCD data is developed at Laboratoire de Météorologie Dynamique du CNRS (Paris, France) [1][2][START_REF] Forget | 5 th Int. Workshop on Mars Atmosphere Modeling and Observations[END_REF] in collaboration with LATMOS (Paris, France), the Open University (UK), the Oxford University (UK) and the Instituto de Astrofisica de Andalucia (Spain) with support from the European Space Agency (ESA) and the Centre National d'Etudes Spatiales (CNES).

The MCD is freely available upon request (contact millour@lmd.jussieu.fr or forget@lmd.jussieu.fr ); a simplified web interface for quick browsing at MCD outputs is available on http://www-mars.lmd.jussieu.fr

Overview of MCD contents:

The MCD provides mean values and statistics of the main meteorological variables (atmospheric temperature, density, pressure and winds) as well as atmospheric composition (including dust and water vapor and ice content), as the GCM from which the datasets are obtained includes water cycle [START_REF][END_REF]5], chemistry [START_REF] Lefevre | 4 th Int. Workshop on Mars Atmosphere Modeling and Observations[END_REF], and ionosphere [START_REF] Gonzalez-Galindo | [END_REF][START_REF] Chaufray | 5 th Int. Workshop on Mars Atmosphere Modeling and Observations[END_REF] models. The database extends up to and including the thermosphere [9,10] (~350km). Since the influence of Extreme Ultra Violet (EUV) input from the sun is significant in the latter, 3 EUV scenarios (solar minimum, average and maximum inputs) account for the impact of the various states of the solar cycle.

As the main driver of the Martian climate is the dust loading of the atmosphere, the MCD provides climatologies over a series of dust scenarios : standard year (a.k.a. climatology) , cold (i.e: low dust), warm (i.e: dusty atmosphere) and dust storm, These are derived from home-made, instrument-derived (TES, THEMIS, MCS, MERs), dust climatology of the last 8 Martian years [START_REF] Montabone | [END_REF]. In addition, we also provide additional "add-on" scenarios which focus on individual Martian Years (MY 24 to 32) for users more interested in specific climatologies than the MCD baseline scenarios designed to bracket reality, Column densities of these species are also given.

 Dust mass mixing ratio, along with estimated dust effective radius and dust deposition rate on the surface are provided.

 Physical processes in the Planetary Boundary Layer (PBL) [12], such as PBL height, minimum and maximum vertical convective winds in the PBL, surface wind stress and sensible heat flux.

 A high resolution mode which combines high resolution (32 pixel/degree) MOLA topography records and Viking Lander 1 pressure records with raw lower resolution GCM results to yield, within the restriction of the procedure, high resolution values of atmospheric variables.

 The possibility to reconstruct realistic conditions by combining the provided climatology with additional large scale (derived from Empirical Orthogonal Functions extracted from the GCM runs) and small scale perturbations (gravity waves), a scheme which has been greatly improved for MCDv5.3.

Improvements in

Figure 1 :

 1 Figure 1 : Illustrative example of the online Mars Climate Database web interface and its plotting capabilities.

  Provided outputs: The MCD provides users with:  Mean values and statistics of main meteorological variables (atmospheric temperature, density, pressure and winds), as well as surface pressure and temperature, CO2 ice cover, thermal and solar radiative fluxes, dust column opacity and mixing ratio, [H20] vapour and ice concentrations, along with concentrations of many species: [CO], [O2], [O], [N2], [Ar], [H2], [O3], [H] ..., as well as electrons mixing ratios.

MCDv5. 3 :

 3 This new version of the MCD includes the following additions and upgrades: Better documentation on guidelines for the integration of the MCD on Windows operating systems.  Improved interfaces with Matlab, Scilab and IDL which are now fully interactive with the MCD (Fortran) software  Improved computation of some of the trace species column densities when in MCD "high resolution" mode.  An improved gravity waves schemes, which accounts for both horizontal and vertical propagation of these.  Improved extrapolation around the MCD "model top" (~10 -8 Pa, i.e. ~250km) to better represent the exosphere where species evolve with their own distinct scale heights. In practice this means that provided compositions and densities should be trusted up to ~500km.  The Mars Year 32 dust scenario has been added.  Updated Extreme UV scenarios to better bracket the latest observed solar cycle (see figures 2 and 3).

Figure 2 :

 2 Figure 2: Solar EUV cycle (in terms of E10.7 proxy) over the last Mars Years. The MCD5.3 EUV minimum, average and maximum cases respectively correspond to E10.7 values of 80, 140 and 320.

Figure 3 :

 3 Figure 3: MCDv5.3 temperature profiles extending into the thermosphere using the three synthetic EUV (minimum, average and maximum) forcings (with the climatology dust scenario), along with the realistic cases obtained at same location and time of year when using the MY24 to MY32 scenarios.

Workshop organized by ESA-ESAC & IAA-CSIC, with the support of the ESAC Faculty and the EU H2020 project UPWARDS


domain: math info

text:
Aimen Daoudi
email: aimen.daoudi@etu.univ-cotedazur.fr

Stéphane Junca
email: stephane.junca@univ-cotedazur.fr

Efficient algorithms computing p-variation

Keywords: AMS Classification: 26A45, 6504, (35L65) p-variation, fractional BV spaces, conservation laws

come

The p-variation, p ≥ 1, is a well-known theoretical tool in Probabilities [START_REF] Peter | Multidimensional stochastic processes as rough paths[END_REF] and Functional Analysis [START_REF] Mansfield | Differentiability of Six Operators on Nonsmooth Functions and p-Variation[END_REF][START_REF] Mansfield | Concrete functional calculus[END_REF]. The introduction of the p-variation is due to L.C. Young [START_REF] Chisholm | An inequality of the Hölder type, connected with Stieltjes integration[END_REF] after N. Wiener for p = 2 [START_REF] Wiener | The quadratic variation of a function and its Fourier coefficients[END_REF]. It allows functions with low regularity, typically exhibiting a fractional derivative s = 1/p ≤ 1 [START_REF] Bourdarias | Fractional BV spaces and first applications to scalar conservation laws[END_REF]. The interest in effectively computing the p-variation is very recent. The first general algorithm for computing the p-variation was proposed by Vygantas Butkus and Rimas Norvaisa [START_REF] Butkus | Computation of p-variation[END_REF], primarily for applications in probability. This algorithm is referred to as 'Merge'. In this work, two new algorithms, 'Eraser' and 'AOP,' are presented, along with the 'Merge' algorithm applied in a slightly different context. Let's provide an initial insight into the difficulty associated with computing the p-variation

For p = 1, the 1-variation, known as the total variation is the well-known semi-norm related to BV , the space of functions with bounded variation, and it is easy to compute. For p > 1, there are a few rare explicit computations of the p-variation for specific functions in [START_REF] Bruneau | Variation totale d'une fonction[END_REF][START_REF] Castelli | Smoothing effect in BV Φ for entropy solutions of scalar conservation laws[END_REF]. The general case is indeed complicated. For a finite sequence u = (u(1), . . . , u(N )), N ≥ 2 the p-variation is,

p-TV u := sup σ⊂{1,...,N } p-sum σ u, (1.1)
p-sum

σ u = |σ|-1 i=1 |u (σ(i + 1)) -u (σ (i))| p , (1.2)
Where the supremum is taken over all subdivisions of 1, . . . , N . A subdivision σ is an ordered subset of 1, . . . , N . The cardinal or length of σ is denoted by |σ|.

A p-sum of a sequence is the p-sum involving all the terms of the sequence. The notation p-sum , u without referring to a subdivision denotes the sum of all consecutive variations of u at the power p.

p-sum u := p-sum

(1,...,N )

u = N -1 i=1 |u (i + 1) -u (i)| p . (1.3)
The cost of computing a p-sum of a sequence u is simply of order N . In contrast, the number of subdivisions is prohibitive, on the order of 2 N . Thus, computing a p-variation of u directly as the maximum of all p-sum corresponding to all subsequences of u is too expensive. A strategy to compute p-TVu is to find an optimal subdivision σ ⋆ such that p-TV u = p-sum σ * u. That is to find an optimal subsequence u ⋆ = (u(i)) i∈σ ⋆ such that p-TV u = p-sum u ⋆ . In this paper, we propose some algorithms to find u ⋆ efficiently.

Notice that extensive use of subsequences is made in this paper for p > 1. Therefore, the chosen notation for sequences is the same as that for functions. A value in a sequence is denoted u(n) instead of u n because it is more readable. Thus, for a subsequence, we prefer to use the notation u(σ(k)) instead of u σ(k) or u σ k .

In general, only for p = 1 this supremum is easy to compute, thanks to the triangular inequality, the whole subdivision σ * = {1, . . . , N } always yields the supremum. And the cost of this computation is simply N . That is for p = 1, T V u = p-TVu = p-sum u := p-sum For p > 1, it is more complicated. The whole subdivision is not usually optimal to compute the supremum. For instance, let u be an increasing sequence, u ∈ R N +1 , where

u(i) = i -1 N , i = 1, . . . , N + 1.
In this case, if all of the (N + 1) points of u are taken, then, when N → +∞,

p-sum u = N i=1 |u (i + 1) -u (i)| p = N 1 N p = 1 N p-1 → 0.
But if the first term and the last one are taken, that is the subdivision σ * = {1, N }, then the greatest p-sum is achieved. Thus, the p-variation is,

p-TV u = p-sum (1,N +1) u = |u(N + 1) -u(1)| p = |1 -0| p = 1.
Also, taking the first and the last values of the sequence is not always the optimal choice, for example, u = (u(1), u(2), u(3)) = (0, 9, 0), here |u(1) -u(3)| p = 0. But if we take all the terms of the sequence u, we get 2

-TV u = |u(1) -u(2)| 2 + |u(2) -u(3)| 2 = 162.
As a consequence, an optimal subdivision to compute the supremum is not known by advance (except in special cases). Starting from the definition, a naive algorithm is to take the maximum of the summations for all subdivisions which has a prohibitive exponential cost. Algorithms with a polynomial cost only appear recently [START_REF] Butkus | Computation of p-variation[END_REF][START_REF] Daoudi | Algorithms for fractional BV norms[END_REF][START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF]. In this paper, three algorithms are proposed "AOP", "Eraser" and "Merge". The two first are new. The third one was already found by Buktus and Norvaisa [START_REF] Butkus | Computation of p-variation[END_REF]. The exact cost is still not completely solved. It is at least N 2 and at most N 3 . A recent preliminary numerical study [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF] suggests that "AOP" is the simplest and the fastest algorithm. But there is room to improve the cost of "Eraser" and "Merge". In particular, a fourth algorithm to improve "Eraser" and "Merge", called "MEI" is proposed in [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF] but not studied here.

The paper is organized as follows. In Section 2, mathematical tools are given in a selfcontained way to validate mathematically all the algorithms presented. This long fundamental section is the largest part of the document Then the algorithms "Eraser", "Merge" and "AOP" are presented in Section 3. The polynomial efficiency of the algorithms are discussed in Section 4. Finally, a presentation of the motivations to compute the p-variation and the relation with fractional BV spaces are presented in the appendix.

On p-variation

To build efficient algorithms to compute p-variation also called the p-total variation, many useful properties and definitions are provided in this section. It is well known that a subsequence is needed to compute the p-variation of a sequence [START_REF] Bourdarias | Fractional BV spaces and first applications to scalar conservation laws[END_REF][START_REF] Bruneau | Variation totale d'une fonction[END_REF][START_REF] Butkus | Computation of p-variation[END_REF], that is to replace a supremum on a large set by a sum. Only for some special examples, the p-variation can be reached for the whole sequence in Section 2.1. These examples can be used to test algorithms computing the p-variation. The fundamental results to build general and efficient algorithms to compute the pvariation are given in Section 2.2. This section is self-contained. Other presentations can be found in the book [START_REF] Bruneau | Variation totale d'une fonction[END_REF] by Michel Bruneau and in the first article presenting an efficient algorithm by Vygantas Butkus and Rimas Norvaisa [START_REF] Butkus | Computation of p-variation[END_REF].

Examples and properties of optimal sequences

We start with basic notions required throughout the paper.

It is said that a sequence u = (u(i)) 1≤i≤N has no constant step if ∀i : 1 ≤ i < N, u(i) ̸ = u(i + 1).
The sequence u also only has extreme values if

∀i : 1 < i < N (u(i) -u(i + 1))(u(i) -u(i -1)) ≥ 0.
That means that all values of u are extreme values, i.e. local maximum or local minimum:

u(i) ≥ max(u(i -1), u(i + 1)) or u(i) ≤ min(u(i -1), u(i + 1)).
It is convenient also to consider only strict extrema. The sequence u only has strict extreme values if

∀i : 1 < i < N (u(i) -u(i + 1))(u(i) -u(i -1)) > 0.
In this case the sequence cannot be constant, has no constant step and it is an oscillating sequence. An oscillating sequence is a sequence such that for all 1 < i < N ,

sign(u(i + 1) -u(i)) = -sign(u(i) -u(i -1)).
The extreme values of a sequence give the first reduction of the size of a sequence to compute the p-variation (p > 1). Indeed, the p-variation of a sequence can be computed on the subsequence consisting of all its extreme values.

Proposition 2.1 ([2]

). Let v be the subsequence of all extreme values of u, then p-TVu = p-TVv.

Notice that if u has no constant step, the subsequence v containing all extreme values and with no constant step has only strict extreme values. The result of the proposition is given in [START_REF] Bourdarias | Fractional BV spaces and first applications to scalar conservation laws[END_REF][START_REF] Bruneau | Variation totale d'une fonction[END_REF] with a simple detailled proof in the appendix of [START_REF] Haspot | Fractional BV solutions for 2×2 system of conservation laws with a genuinely nonlinear field and a linearly degenerate field[END_REF].

The next proposition shows that for large p the optimal subsequence of u = u(1), . . . , u(n)) to compute the p-variation is simply (u(1), u(N ) under the condition that the global maximum and minimum of u are only reached at the boundaries. This result is known for monotonic sequence [START_REF] Bourdarias | Fractional BV spaces and first applications to scalar conservation laws[END_REF][START_REF] Bruneau | Variation totale d'une fonction[END_REF] but here no monotonicity is required.

Proposition 2.2. Let u = (u(1), . . . , u(N )) be a finite sequence. Assume that ∀i such that 1 < i < N , u(1) < u(i) < u(N ).

(2.1)

Then ∃ p 0 such that for all p > p 0 > 1 there is only one optimal subdivision σ ⋆ = {1, N } and,

p-TVu = |u(1) -u(N )| p .
Proof. Let {σ(1), σ(2), ..., σ(m)} a subdivision of {1, ..., N }, where m ≤ N. We are looking to get a p 0 such that ∀p ≥ p 0 , we have:

m-1 l=1 |u(σ(l)) -u(σ(l + 1))| p ≤ |u(σ(N )) -u(σ(1))| p ,
we denote R as the following:

R = m-1 l=1 u(σ(l)) -u(σ(l + 1)) u(σ(N )) -u(σ(1)) p ≤ 1.
Let be ρ,

ρ = max i̸ =j 1<i,j<N u(i) -u(j) u(1) -u(N ) , ρ < 1 from assumption (2.1), therefore, 0 ≤ R ≤ m-1 l=1 ρ p = (m -1)ρ p ≤ N ρ p -→ p→∞ 0.
The convergence towards 0 is uniform w.r.t. the subdivision, thus ∃p 0 , R < 1 for p ≥ p 0 and for all subdivisions. It means that p-TVu[σ] ≤ |u(1) -u(N )| p for p ≥ p 0 and therefore, p-TVu = |u(1) -u(N )| p .

Next, Proposition 2.3 shows that an optimal subsequence always contains the terms where the sequence reachs its maximum, its minimums, the first term and the last term of the sequence u.

Proposition 2.3. Let u = (u(1), . . . , u(N )) be a sequence with no constant step, then all indexes of the global maximum, the global minimum, and the first and the last terms of u are always in any optimal subdivision σ ⋆ , i.e., {1,N} ∪ arg max u ∪ arg min u ⊂ σ ⋆ .

Proof. Let σ ⋆ be an optimal subsequence. 1 Assume first that 1 and N does not belong to σ⋆ then consider σ = {1} ∪ σ ∪ {N } p-sum

σ ⋆ u = |σ ⋆ |-1 l=1 |u(σ ⋆ (l)) -u(σ ⋆ (l + 1))| p < |σ ⋆ |-1 l=1 |u(σ ⋆ (l)) -u(σ ⋆ (l + 1))| p + |u 1 -σ ⋆ (1)| p + |u N -σ ⋆ (|σ ⋆ |)| p = p-sum σ u.
Notice that the strict inequality is a consequence that u has no constant step so

|u 1 - σ ⋆ (1)| p + |u N -σ ⋆ (|σ ⋆ |)| p > 0.
Then the subdivision σ ⋆ is not optimal. That means that 1 and N must belong to σ ⋆ . Now we prove that all indexes of the global maximum and the global minimum of the sequence u belong to σ ⋆ . Assume the negation. Then, there is one of the indexes of the maximum or minimum of u not belonging to the optimal subdivision σ ⋆ , i.e. there exists two indexes k 1 , k 2 such that:

σ ⋆ (1) < k 1 < σ ⋆ (|σ ⋆ |) -1, σ ⋆ (1) < k 2 < σ ⋆ (|σ ⋆ |),
, where one of the indexes of maximum of u is between σ ⋆ (k 1 ) and σ ⋆ (k 1 + 1),(resp. one index of minimum of u is between σ ⋆ (k 2 ) and σ ⋆ (k 2 + 1)). Therefore, p-sum

σ * u = |σ ⋆ |-1 l=1 |u(σ ⋆ (l)) -u(σ ⋆ (l + 1))| p < |σ ⋆ |-1 l=1 |u(σ ⋆ (l)) -u(σ ⋆ (l + 1))| p +|u max -u(σ ⋆ (k 1 + 1))| p + |u max -u(σ ⋆ (k 1 ))| p +|u min -u(σ ⋆ (k 1 + 1))| p + |u min -u(σ ⋆ (k 1 ))| p .
Thus that σ ⋆ is not optimal. Now, the previous result is illustrated by the following oscillating example where σ ⋆ = {1, . . . , N }. Indeed, it is the simplest way to no reducing the sequence for a sequence having no constant step. An oscillating sequences with only two values c 1 ̸ = c 2 is defined by:

u(i) = c 1 , for i even number c 2 , for i odd number (2.2)
Another example used in [START_REF] Bourdarias | Fractional BV spaces and first applications to scalar conservation laws[END_REF][START_REF] Castelli | On the maximal smoothing effect for multidimensional scalar conservation laws[END_REF] where u is already an optimal sequence is now given. A sequence u = (u(1), . . . , u(N )) has a decreasing amplitude means that:

|u(i) -u(i + 1)| ≤ |u(i + 1) -u(i + 2)| , ∀i : 1 ≤ i ≤ N -2. u (2)
u( 4) u( 6) u( 1) u( 3) u( 5) u( 7) The next proposition 2.4 shows that if the sequence u has a decreasing amplitude then the optimal subsequence also is the same sequence u.

Proposition 2.4 ([2]

). Let u = (u 1 , . . . , u N ) an oscillating sequence with no constant step that has a decreasing amplitude than, u = u ⋆ , and σ ⋆ = {1, . . . , N }.

u

u( 4)

u(2)
Figure 3: A sequence with decreasing amplitude A detailled proof is in [START_REF] Castelli | On the maximal smoothing effect for multidimensional scalar conservation laws[END_REF], Proposition 10.

Main tools to build an optimal subsequence

The main tools to build the algorithms is given in this section. By definition of the p-variation of any finite sequence u, there exists a subsequence u * of u such that p-sum u * = p-TVu. How to build u * ? We proceed step by step. We start with the whole sequence. Then the following test has done on the j+1 consecutive terms after

u i . If |u i+j -u i | p ≥ j l=1
|u i+l -u i+l-1 | p then the subsequence v with all the terms of u except the j -1 consecutive terms u i+1 , . . . , u i+j-1 seems to be a smaller sequence with the same p-variation, p-TVv = p-TVu. If it is the case, we can continue, continue, . . . and finally expect to reach an optimal subsequence w of u such that p-TVw = p-sum w = p-TVu.

Here, we will prove that such strategy work well if we do such tests in the right order. This strategy corresponds to the natural "Eraser" algorithm presented below.

The following condition is then a fundamental condition to check,

H < ij = H < ij (u) : |u(i + j)-u(i)| p < j l=1 |u(i + l)-u(i + l -1)| p , 2 ≤ j < N. (2.3)
When there is no ambiguity on the sequence u considered the short notation

H < ij is used instead of H < ij (u).
In the same way we define

H = ij , H ≥ ij , H > ij . For instance H = ij means, H = ij : |u(i + j) -u(i)| p = j l=1 |u(i + l) -u(i + l -1)| p . (2.4)
We will see below that if H < ij is true for all i and all j then u is already and optimal sequence to compute its p-variation. To shorthen the notations,

H ≤ j means that all inequalities H ≤ ij , i = 1, . . . , N -j are satisfied where 2 ≤ j < N .
This fundamental proposition characterizes optimal sequences.

Proposition 2.5 (Optimal sequence to compute p-TV).

Let p > 1 and u = (u(1), . . . , u(N )). p-TVu = p-sum u if and only if all inequalities H ≤ j (u) are true, j = 2, . . . , N -1. In practice, if all strict inequalities H < ij (u) are true, u is an optimal sequence to compute p-TVu. This last criteria is preferred because it allows to reduce the size of the subsequence. Less terms has a sequence, less expansive is the cost of computing a p-sum . Let us explain on a simple example the reduction of the size of the sequence on a typical example. Let p = 2 and u be the sequence u = (0, 2a, a, 3a) with a > 0 has exactly two optimal subsequences to compute p-TVu, u = (u(1), u(2), u(3), u(4)) and v = (u(1), u(4)) = (0, 3a) since,

p-TVu = 9a 2 = p-sum v = |0 -3a| 2 = 3 2 a 2 = p-sum u = |0 -2a| 2 + |2a -a| 2 + |a -3a| 2 = 2 2 a 2 + a 2 + 2 2 a 2 .
Proof. By definition of p-TVu, p-sum u ≤ p-TVu is always true. No consider v a subsequence of u associated the a subdivision

σ of length k, v = (u(σ(1), . . . , u(σ(k)). Using inequalities H ≤ ij (u) yield p-sum v = k i=2 |v(i) -v(i -1)| p = k i=2 |u(σ(i)) -u(σ(i -1))| p ≤ k i=2 σ(i)-1 j=σ(i-1) |u(j + 1) -u(j)| p = σ(k) j=σ(1) |u(j) -u(j -1)| p ≤ p-sum u.
Thus p-sum u = p-TVu.

Conversely, if one inequality

H ≤ ij is not satisfied for a couple (i, j) such that 1 ≤ i ≤ N -2, 2 ≤ j ≤ N -i, then H > ij is true. Consider v = (u(1), . . . , u(i), u(i + j), . . . , u(N )) the subsequence of u without the j -1 terms u(i + 1), • • • , u(i + j -1), then p-sum u = i-1 l=1 |u(l + 1) -u(l)| p + i+j-1 l=i |u(l + 1) -u(l)| p + N 1 l=i+j |u(l + 1) -u(l)| p < i-1 l=1 |u(l + 1) -u(l)| p + |u(i + j) -u(i)| p + N 1 l=i+j |u(l + 1) -u(l)| p = p-sum v.
Thus, u is not an optimal sequence and the proposition is proven.

The goal of this paper is to look for a subsequence v of u and compute p-TVu with the p-sum v. That is transforming a problem with, at a first sight, an exponential cost, by a p-sum which has a linear cost. The main idea is to use check inequality H < ij and when it is false to erase all the terms between u(i) and u(i + j) to build a subsequence v without loosing p-TVu. The subsequence has to satisfies p-TVv = p-TVu. When the subsequence satisfies Proposition 2.5, that is v is an optimal sequence to compute p-TVv with p-sum v, then p-sum v = p-TVv = p-TVu. If v does not satifies the proposition then continue the extraction of a subsequence, etc . . . To use such a strategy, we have to be careful. Starting the test of inequlity H < ij on long length of consecutive terms, i.e. large j, and finishing by small length can be a very bad idea. For instance, consider the sequence u = (1, 0, 1, 2, 3) with 5 terms. The condition

H < 14 is false. If the sequence v = (u(1), u(6)) = (1, 4) is extracted then p-sum v = 9 < (1 -0) 2 + (3 -0) 2 = p-TVu = 10.
The next proposition overcomes this possible difficulty. Indeed, Proposition 2.6 gives sufficient conditions to have only one subsequence to compute the p-variation when inequality

H ≤ 1(N -1) is false Proposition 2.6. [When H ≥ 1(N -1) yields the p-variation ] Let p > 1, u = (u(1), . . . , u(N )), u * = (u(1), u(N )) and N ≥ 3. If the inequality H < 1(N -1)
is false but for all j < N -1 the inequalities H < j are true then, (P1) The sequence u has no constant step and u(1) ̸ = u(N ).

(P2) u * is an optimal subsequence of u, p-TVu = p-sum u * = |u(1) -u(N )| p > 0. (P3) If H > 1(N -1)
is satisfied, then, u * is the unique optimal subsequence to compute p-TVu, p-TVu = p-sum u * .

(P4) If the equality H = 1(N -1) is true then there are exactly two optimal subsequences, the shortest u * and the longest u, p-TVu = p-sum u * = p-sum u.

(P5) {u(1), u(N )} = {min u, max u} and min u < u(i) < max u , where 1 < i < N.

Notice that, in general, if u has pnly one constant step there is maybe no uniqueness of an optimal subsequence to compute p-TV. Fo instance u = (u(1), u(2), u(3)) = (1, 2, 2) has three subsequences to compute the p-variation (u(1), u(2)) , (u(1), u(3))and u = (u(1), u(2), u(3)).

Proof. The inequality

H < 1(N -1) is false means H > 1(N -1) or H = 1(N -1
) is true, Now, all properties can be proved.

For (P1): The conditions H < i2 are true for all i ≤ N -2 means

0 ≤ |u(i + 2) -u(i)| p < |u(i + 1) -u(i)| p + |u(i + 2) -u(i + l)| p .
The inequality is strict so

|u(i + 1) -u(i)| > 0 or |u(i + 2) -u(i + 1)| > 0.
But, if one term is zero there is an inequality. Thus, the two terms are positive. This property is true for all 1 ≤ i ≤ k -2, so u has no constant step.

Hence, all the terms on the right hand side of inequality H > 1(N -1) are positive and

|u(1) -u(N )| > 0, i.e. u(1) ̸ = u(N ). For (P2): Let is v a subsequence of u. If v = u * then p-sum v = |u(1) -u(k)| p = p-TVu * . If v = u then p-sum v = p-sum u < p-TVu * by inequality H > 1(N -1)
. Now, in all the sequel, only the case u ̸ = v ̸ = u * is considered. So, some terms of the sequence u are missing in v. That means that there exists i and j < k -1 such that the terms u(i), u(i + j) are in v but not u(i + l) for all 0 < l < j. However, inequality H < ij is true since j < k -1. Now, consider the sequence w containing all the v terms and filling the gap between u(i), u(i + j) by all the terms u(i + l) for all l = 1, . . . , j -1. So u is a subsequence of w, w is a subsequence of u and,

(p-sum w) -(p-sum v) = j-1 l=1 |u(i + l) -u(i + l + 1)| p -|u(i + j) -u(i)| p > 0 since inequality H < ij is true. That means p-sum v < p-sum w.
Continuing to fill all the gaps of v in the same way and using the fact that all corresponding H < ij are true finally yields, p-sum v < p-sum u.

(2.5)

The last inequality is so important that we rewrite the proof by a direct computation.

If v ̸ = u * and v ̸ = u then, there exists a subdivision σ with length L < k such that v = (u(σ(i)), i = 1, . . . , L) and,

p-sum v = L i=2 |u(σ(i) -u(σ(i -1)| p < 1<i≤L σ(i-1)<l≤σ(i) |u(l) -u(l -1)| p = p-sum u.
Notice that at the second line that the inequality is strict because, v has at least one term less than u because v ̸ = u, and at most k -3 consecutive terms less than u because v ̸ = u * . The corresponding condition H < ij for these missing consecutive terms is true. Thus, Inequality (2.5) is proved. Now, we can conclude from the inequality (2.5). Since For (P3): This is a consequence of the proof of (P2).

For (P4): In case of equality there are two subsequences, one is u with the maximal length and the other one u * with the minimal length. Notice that the equality is always possible.

For p = 2 it suffices to take this minimal example [START_REF] Bourdarias | Fractional BV spaces and first applications to scalar conservation laws[END_REF], u = (0, a, a-b, 2a+b) with 0 < b < a and b = a/2. For 1 For (P5): by the proposition (2.3), we can get that the indexes of maximum and minimum of (u n ) 1≤n≤k are in σ ⋆ = (1, N ), since its length is 2 and by (P1) u(1) ̸ = u(N ) . Moreover, that means that the extrema of the sequence u are only reached at the boundary {1, N }, thus (P3) is proved.

< p ̸ = 2,
The next result generalizes Proposition 2.6 and it will be used later to validate all algorithms presented in this paper Theorem 2.1 (subsequence containing an optimal one).

Let p > 1 and u = (u(1), . . . , u(N )), where

N ≥ 3, let k ≤ N . If H < j , 2 ≤ j < k, H < 1k , H < 2k , .
.., H < (α-1)k are true, and H < αk is false. then, there exists an optimal subsequence u * and its optimal subdivision σ * to compute p-TVu such that,

u * ⊂ (u(1), . . . , u(α), u(α + k), . . . , u(N )), σ * ∩ {α + 1, ..., α + k -1} = ∅.
Proof. Proposition 2.6 yields that the extrema of u on the interval α ≤ l ≤ α + k are only reached for the terms u(α) and u(α + k). To fix the notations assume that

1. u(α) = min α≤l≤α+k u(l). 2. u(α + k) = max α≤l≤α+k u(l). 3. u(α) < u(i) < u(α + k) for all α < i < α + k.
If it is not the case, it suffices to multiply the sequence -1. Now, for any subdivision σ ⊂ {1, ..., N } a suitable subdivision τ is built such that,

τ ∩ {α + 1, ..., α + k -1} = ∅ and p-sum σ u ≤ p-sum τ u.
For this purpose, let σ a subdivision with cardinal ν defined by,

σ = σ ∩ {α + 1, ..., α + k -1} .
Depending on ν there are 3 cases to consider, ν = 1, ν = 2, and ν ≥ 3.

First, when ν = 1, σ has only one element called δ, σ = {δ}.

Let β be the largest index in σ less than α, and γ be the smallest in σ greater than α + k,

β < α < α + k < γ.
Now, they are only four possibilities illustrated in Figures [START_REF] Bourdarias | Entropy solutions in BV s for a class of triangular systems involving a transport equation[END_REF][START_REF] Bruneau | Variation totale d'une fonction[END_REF][START_REF] Butkus | Computation of p-variation[END_REF][START_REF] Castelli | Oscillating waves and optimal smoothing effect for one-dimensional nonlinear scalar conservation laws[END_REF]. The subdivision τ is built for each case: Second, when ν = 2, i.e. σ = {δ, ϵ}. Let σ -= σ -σ. Since the sequence {α, δ, ϵ, α + k} has 4 terms, there are more cases. Indeed 8 where τ is defined as follows,

case 1 u(β) ≥ u(α) and u(α + k) ≥ u(γ). τ = (σ -{δ}) ∪ {α, α + k}. case1 : u(α + k) u(β) u(δ) u(γ) u(α)
case 1.1 u(β) ≥ u(α), u(α + k) ≥ u(γ) and u(δ) < u(ϵ) τ = σ -∪ {α, α + k} case 1.2 u(β) ≥ u(α), u(α + k) ≥ u(γ). and u(δ) > u(ϵ) τ = σ -∪ {α, α + k} case 2.1 u(β) < u(α), u(α + k) < u(γ) and u(δ) < u(ϵ) τ = σ - case 2.2 u(β) < u(α),u(α + k) < u(γ) and u(δ) > u(ϵ) τ = σ - case 3.1 u(β) < u(α), u(α + k) ≥ u(γ) and u(δ) < u(ϵ) τ = σ -∪ {α + k} case 3.2 u(β) < u(α), u(α + k) ≥ u(γ) and u(δ) > u(ϵ), τ = σ -∪ {α + k} case 4.1 u(β) ≥ u(α),u(α + k) < u(γ) and u(δ) < u(ϵ) τ = σ -∪ {α} case 4.2 u(β) ≥ u(α), u(α + k) < u(γ) and u(δ) > u(ϵ) τ = σ -∪ {α}
Third and final case ν ≥ 3, σ = {δ(1), ..., δ(ν)}.

For the sequence (u(l)) δ( 1)≤l≤δ(M ) which is u restricted to σ, the inequalities H < δ(1)j are true, where j = δ(ν) -δ(1), thus, Let σ -= σ -{δ(2), . . . , δ(ν -1)} and build τ as when ν = 2, completing σ -or not with {α, α + k}, according to the previous eight cases.

|u(δ(ν)) -u(δ(1))| < δ(ν-1) i=δ(1) |u(σ(δ(i))) -u(σ(δ(i + 1)))| p < α+k-1 i=α |u(σ(δ(i))) -u(σ(δ(i + 1)))| p ≤ |u(α) -u(α + k)| p . case3 : u(α + k) u(δ) u(γ) u(α) u(β)
Next Proposition 2.7 shows that inequalities H < j , where j is odd are consequence of the same inequalities for smaller j when the sequence has no constant step. Proposition 2.7 (Only even number of consecutive terms to check). Let u = (u(1), . . . , u(N )) be a sequence that has only local extrema and non constant step. If all inequalities H < j are true for all 2 < j ≤ 2k -1, then, H < 2k is true.

The number of consecutive terms in the inequality H < ij is j + 1 . The proposition means that the H < ij has to be checked for j + 1 even so j odd. Notice that H < 2 is true since the sequence has only local extrema and nonconstant step.

case1 -1 : Proof. Assume that inequalities H < j are true for all 2 < j < 2k. Let i be fixed such that i + 2k ≤ N . The goal is to prove that H < i,2k is true. Since the sequence u has only extrema and j is even, thus,

u(α + k) u(β) u(δ) u(γ) u(ϵ) u(α) case1 -2 : u(α + k) u(β) u(γ) u(ϵ) u(δ) u(α)
u(i) < u(i + 1), u(i + 1) > u(i + 2), • • • , • • • , u(i + 2k -2) < u(i + 2k -1), u(i + 2k -1) > u(i + 2k).
If the above inequalities are in the reverse order, it suffices to multiply the sequence by (-1). They are two cases.

1. if u(i) ≥ u(i+2k) then u(i+1) > u(i+2k) and |u(i)-u(i+2k)| < |u(i+1)-u(i+2k)|. Now, using inequality H < i+1,2k-1 yields |u(i) -u(i + 2k)| p < |u(i + 1) -u(i + 2k)| p < 2k-1 l=1 |u(i + l) -u(i + l + 1)| p < 2k-1 l=0 |u(i + l) -u(i + l + 1)| p .
That means that H < i,2k is true. u(i + 2k) < u(i + 2k -1). Now, using inequality

2. if u(i) < u(i + 2k) then |u(i) -u(i + 2k -1)| > |u(i) -u(i + 2k)| since u(i) < case2 -1 : u(γ) u(α + k) u(δ) u(ϵ) u(α) u(β) case2 -2 : u(γ) u(α + k) u(ϵ) u(δ) u(α) u(β)
H < i,2k-1 yields |u(i) -u(i + 2k)| p < |u(i) -u(i + 2k -1)| p < 2k-2 l=0 |u(i + l) -u(i + l + 1)| p < 2k-1 l=0 |u(i + l) -u(i + l + 1)| p .
That means again that H < i,2k is true.

Therefore, the condition H < i2k is always true for all i and H < 2k also. All of these properties are used to build polynomial algorithms in section 3. The point is to construct many subsequences before computing the p-variation of an initial sequence as the p-sum of the final subsequence built.

Algorithms to compute p-variation

In this section, algorithms are presented to compute the p-TV semi-norm of a sequence u = (u(1), ..., u(N )) and p > 1. Starting with the definition of p-TVu, a first naive algorithm is the following.

case3 -1 : This algorithm is implemented in [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF]. It is too costly. The number of subdivisions is of order 2 N thus the cost is at least 2 N . Moreover, the computation of a p-sum is of order N thus, the algorithm "Exhaustif" is at most of order N 2 N . It can only be used when the number N of data is small. It is the reason why other algorithms are proposed in this paper.

u(α + k) u(δ) u(ϵ) u(α) u(β) case3 -2 : u(α + k) u(ϵ) u(δ) u(α) u(α) u(γ) u(β)

"Eraser"

The principle of "Eraser" is to build a subsequence of u called u * to compute p-TVu with p-sum u * . Thus, transforming a problem with an exponential cost to a problem with a linear cost. Computating a p-sum has a cost of order of the length of the sequence. For this purpose, we know that all inequalities H < ij have to be fullfilled to obtain an optimal subsequence, Proposition 2.5. If it is not the case for an inequality, as in Proposition 2.6, we can extract a subsequence. Indeed, if inequality H < ij is wrong, we can extract a subsequence v of u by erasing all the (j -1) terms between u(i) and u(i + j) and keep p-TVu = p-TVv if all inequalities H < ik are true for k < j, Theorem 2.1. How to implement such algorithm? It suffices to start with j = 2, testing the validity of the inequality H < ij for i = 1, . . . , N -j. If the equalities are true, we continue with j = 3 and so on, increasing j by one if all inequalities H < ij are true for all i. Using Proposition 2.7, j can be increased by 2, to consider only j odd. Thus, the sequence of j is 2, 3, 5, 7, 9, . . .. Only case4 -1 : the first value of j is even to extract from the sequence u, the subsequence containing all the extreme values of u (local maximum and local minimum). Finally, if we reach j = N -1, there is only one inequality to test. If is true, the initial sequence is an optimal sequence and p-sum u = p-TVu.

u(α) u(ϵ) u(δ) u(α + k) u(β) u(γ) case4 -2 : u(α) u(δ) u(ϵ) u(α + k) u(β) u(γ)
A problem occurs if, during this process, one inequality H < ij (u) is not true. We can erase the terms between u(i) and u(i + j), obtaining a subsequence v which has the same p-variation as u. Notice that inequality H < i2 (v) can be false, because it involves v(i) = u(i), v(i + 1) = u(i + j), v(i + 2) = u(i + j + 1). Thus, to apply Theorem 2.1, we have to check all inequalities H < kq with all q ≤ j, k such that the subsequence (v(k), v(k + 1), . . . , v(k + q)) involves v(i) and v(i + 1). If all such inequalities are true, we can continue the process for k = i + 1 and q = j. A simple way to check these inequalities for v is to restart the process at the beginning with the sequence v instead of the sequence u, that is

H < 12 (v), H < 22 (v), H < 32 (v)
, and so on. In the following algorithm, "com:" means commentary.

Algorithm 1a: "Eraser"

Eraser.0(u,p) com: Input: sequence u, p > 1 1. u:= all extreme points of the sequence u 2. N:= size(u) 3. For j = 3 to N -1, j odd, do

4.

For i = 1 to (N -j) do

5.

If H < ij is false then com: "Erase" u(i + 1), . . . , u(i + j -1), j -1 terms of u to extract a subsequence:

6. u:= the subsequence of i without the j-1 terms between u(i) and u(i + j) com:

Break, restart at the beginning,

7.

Goto line 1.

8.

End If

9.

End do 10. End do

Result: u

The programm certainly finishes because there is only a finite number of tests and the size of the subsequence decreases after each extraction and yields to a final subsequence z. Moreover, at the end, all inequalitoes H < ij (z) are fulfilled, thus p-TVu = p-TVz = p-sum z. The first version of "Eraser", "Eraser.0" can be improved.

After one erasing, when H < ij (u) is false, the subsequence v = (u(1), . . . , u(i), u(i+1), u(N )) has the size N = N -(j -1). Only the inequalities H < kq , q < j or q = j and k + j = i + 1, involving v(i) and v(i + 1) has to bo done. The other one for too small k or too big k have already been tested in the sequence u. That means for q < j, k ≤ i ≤ i + 1 ≤ k + q, that is k beetween i + 1 -q and i. These local tests containing the terms u(i) and u(i + j) = v(i + 1) are less costly than restarting the program with the sequence v instead of the sequence u. If all the tested inequalities H < kq , q < j are valid, then the initial process is continued with k = i + 1 -j and the inequality H < kj . Else, an extraction occurs for a fixed k 1 and q < j, and local tests has to be done around v(k 1 ) and v(k 1 + 1) that is doing the local tests with i = k 1 . Algorithm 1b: "Eraser" improved Eraser.1(u,p) 1. Extract only extreme points from the sequence u and N =size(u) 2. For j = 3 to N -1, j odd , do

3. i := 1 4. Repeat 5.
If H < ij is false Then "erase" the j-1 terms between u(i) and u(i + j)

6.

For q = 2 to j -1, q = 2 or q odd, 7.

For k = i + 1 -q to i do,

8.

If H < kq is false then "erase"; i:=k and go to line 6

"Merge"

The first efficient algorithm to compute p-variation was built by Vygantas Buktus and Rimas Norvaisa [START_REF] Butkus | Computation of p-variation[END_REF] for applications in Probabilities which are based on the famous algorithm "divide and conquer". Recently other algorithms are proposed in [START_REF] Daoudi | Algorithms for fractional BV norms[END_REF][START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF]. A natural question concerns the initialization of such an algorithm to reduce the number of merging. Recently, an interesting idea was proposed in [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF] to improve Merge and Eraser with the algorithm "MEI" explained at the end of this subsection.

The principle of "Merge" is as follows. Let u = (u(1), . . . , u(n)) and v = (v(1), . . . , v(m)) two sequences. If u and v are two optimal sequences, i.e. p-TVu = p-sum u and p-TVv = p-sum v, then, the concatenation of the two sequences L = (u, v) is "almost" an optimal sequence with size N = n + m. This is almost true because already many inequalities are true H < ij . For instance, all inequalities H < 2. L:=empty list Algorithm "MEI" The algorithm "MEI" is the algorithm "Merge" initialised by the algorithm "Eraser": "Merge by Eraser initialisation algorithm". "M" means "Merge", "E" "Eraser" and "I" "initialization". It was first proposed in [START_REF] Butkus | Computation of p-variation[END_REF]. The main idea is to reduce the cost of "Eraser" which try to merge not optimal sequences after each erasing and to improve the initialisation of "Merge".

The principle is the following: take a sequence u = (u(0), ..., u(N )) and start with the Eraser algorithm. Use Eraser algorithm to do all the tests H < ij but after an erasing do not restart at the beginning. In this case two sub-lists are obtained and the tests can be applied independently on the two sub-lists. So, continue to use "Eraser" in the same way on the two sub-lists to obtain more and more lists. Finally the initial list in cut in many independent lists. Moreover, the sub-lists obtained are necessary optimal sequences since they satisfy the tests H < ij . Thus, it is an interesting departure to start to merge all these optimal sub-sequences. Indeed, we have many sub-lists optimized and less points that initially. We can then use the Merge algorithm to merge the list.

"AOP"=Add One Point

The last algorithm, "AOP", is the simplest to implement and seems to be faster than "Eraser" and "Merge" [START_REF] Daoudi | Algorithms for fractional BV norms[END_REF]. Numerical comparisons on thousands examples has be done in [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF]. The basic principle is to merge an optimal sequence with a sequence with only one value and to extract of the new enlarged sequence an optimal subsequence. Let L be a sequence with the length l, to concanete this sequence with a ne w value v, L = (L(1), . . . , L(l), v) and to extract from L a new optimal sequence L , so p-TV L = p-sum L. This can been seen as a special merging. The big advantage of this merging is the cheap cost, very less than merging two optimal sequences with lengths l/2. Indeed, since L is an optimal sequence, the only inequalities H < ij ( L) to check are the inequalities involving the last term v, i.e. i + j = l + 1, so only O(l) inequalities. Now, to extract an optimal subsequence to a given sequence u with length N , we start with the optimal sequence L 1 = (u(1)) with length l 1 = 1, we concanete u(2), L 2 = (u(1), u(2)) and extract for the new sequence an optimal one L 2 . At the step n, L n in an optimal subsequence of (u(1), . . . , u(n), 1 ≤ n ≤ N . The length of L n is l n ≤ n, L n+1 = (L n (1), . . . , L n (l n ), + 1) is a subsequence of (u(1), . . . , u(n + 1). We extract from L n+1 an optimal sequence L n+1 . At the end L N is an optimal sequence of the whole sequence u. Notice also, that the merging is simpler than in "Merge" or in 'Eraser". When we erase (extract a subsequence if H < ij is false), we simply restart the process of checking all inequalities H < ij involving the last term u(n + 1). The algorithm can be shortened starting with a sequence with no constant step. Thus (u(1), u( 2)) is an optimal sequence and we can start with n = 2.

We also compute the p-sum more efficiently to reduce the cost of the algorithm. Now, the algorithm can be written. Optimal sequence, most costly?

The cost of the algorithm depends on the algorithm, the size of the sequence, but also on the sequence itself. The cost is called C(A, N, u), A stands for the algorithm and u for the sequence with N terms. For instance, if the sequence is constant or increasing, the cost is only N . This is the order of the price of the preprocessing. We consider here the maximal cost C(A, N ) = max u C(A, N, u).

Many numerical test suggest that the cost is maximal when the sequence is already optimal [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF]. It seems that is a consequence of the supposed power-law cost with a power at least 2. There is an heuristic explanation of this fact. To explain this fact, one algorithm is chosen, "Eraser" for instance. Let C(N, u) = C("Eraser", N, u). Forgetting the multiplicative constant giving C(N, u), assume that C(N, u) = N 2 when the initial sequence is already optimal, i.e. no erasing. No compare this cost when there is only one erasing, i.e. one subsequence extracted to obtain an optimal sequence. Due to the preprocessing, if some points are erased to the initial sequence there are at least two points erased. The initial sequence has no constant step and only local extrema. Consider the case with 2 points erased, then the subsequence v has N -2 terms. That means that many inequalities H < i3 have been done before the erasing of two points. Loosely speaking, let's say this cost is N because there are less than N tests to do. Finally, the cost to check that v is an optimal sequence is the cost to find which two consecutive points in u have to be erased and the cost to check that v with N -2 terms is an optimal sequence. That is,

C(N, v) = N + (N -2) 2 = N 2 -3N + 4 < C(N ) = N 2 .
The inequality is at least true for N large enough. We suspect that the optimal sequence are the most costly or at least, such sequences give good insight about the usual complexity of the algorithms. As a consequence, the complexity of the algorithms are next studied only for an optimal sequences. Further studies are needed to obtain the cost of the algorithms for the general case.

Cost comparisons of the three algorithms

In this section, the complexity of the three algorithms are done on the most expensive suspected sequence, that is to say when the sequence is already optimal. The cost is counted with the number of tests done. We suppose that the computations of p-sum are optimised as it is discussed above and as it was done in [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF] for "AOP" and "Eraser". The optimisation of p-sum is more complicated for "Merge". Next, a comparison of these algorithms is discussed.

Eraser

The cost of Eraser on an optimal sequence is simply the cost to check all inequalities in Proposition 2.5. Thus the cost is N 2 in this case.

AOP

We compute the number of tests that "AOP" does on an optimal sequence. All the tests with k points means to check inequality H < j with j = k -

.. + (N -1)) = 2 + N/2 j=2 (2j -1) ∼ N/2 j=2 (2j -1) = N/2 -1 2 (N + 2) ∼ N 2 4 .
Like Eraser, the cost is of order N 2 .

Merge

To compute the cost of "Merge", we first have to compute the cost of the merging of two optimal sequences with the same size M yielding to an optimal sequence. We consider only this case since the cost of "Merge" is done on an optimal sequence u, and any subsequence v of consecutive terms of u is also optimal. Then we have 3 + 5 + ... + M -1 tests to do which yield to a total number of tests of order M 2 . Now, the cost of "Merge" for an optimal sequence with N = 2 k terms is the number of operations for a merging times the number of merging.

The first merging 2

1 2 • (2) k-2 , The second merging 2 2 2 • (2) k-3 , . . . . . . The last merging 2 k-1 2 • (2) 0 . Therefore, k-1 j=1 2 j 2 • 2 k-j-1 = 2 k-1 k-1 j=1 2 j = 2 k-1 • 2 • 1 -2 k-1 1 -2 = N • N 2 -1 ∼ N 2 2 .
Again, "Merge" has a cost of order N 2 .

Notice that in "Merge" the last merging with two sequences with N/2 points has a cost with the same order has the whole "Merge" algorithm. The final merging is then the principal part of the "Merge" cost.

Crude bounds for the cost

For an optimal sequence, the cost N 2 is founded when the p-sum are efficiently computed, else the complexity is of order N 3 . What happens if the initial sequence is not optimal? That is when there are some erasing. Let us give a crude bounds to show that the complexity stays polynomial but with a possible increase of the power. Assume that the computations of p-sum are optimised. The same argument works for p-sum not optimised with a greater power. Let u be a sequence with N terms and suppose there are an erasing with k points and then no erasing. The cost to find the points to erase is less than the cost to check all the inequalities H < ij , that is N 2 . Next the subsequence is supposed optimal, so there are (N -k) 2 tests to do. Finally the total cost is bounded by N 2 + (N -k) 2 . If there are e erasing then, by a similar argument, the total cost is less than

N 2 + (N -k 1 ) 2 + (N -k 1 -k 2 ) 2 + . . . (N -k 1 . . . -k e ) 2
≤ N 2 + (N -1) 2 + . . . + (N -(N -1)) 2 ∼ N 3 /3.

Hence the cost for ageneral subsequence is at most N 3 . This is a crude upper bound and the authors expect that the real cost is less or the worst case is very rare. Of course when the p-sum are not optimised, the cost is of order N 4 .

Comparisons of the 3 algorithms

Preliminary numerical tests are done in [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF]. "AOP" seems the best algorithm, followed by "Eraser" and finally by "Merge". Notice that, "AOP" is easier to programm than "Eraser" , and "Eraser" is even easier to programm than "Merge", thus there are room to improve the first studies given in the report [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF]. A possibility is the preliminary study in [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF] can only reflect that optimising the code for "AOP" is easy, for "Eraser" less easier, and more difficult for "Merge". Anyway, this preliminary study of the cost needs further mathematical and numerical works.

A Motivations to compute the p-variation

History on p-variation The p-variation is first used by Norbert Wiener [START_REF] Wiener | The quadratic variation of a function and its Fourier coefficients[END_REF] for p = 2 to get the convergence of Fourier series following Dirichlet for piecewise C 1 functions and then Jordan for BV function. Such spaces are generalized for all p in [START_REF] Love | Sur une classe de fonctionnelles linéaires[END_REF][START_REF] Chisholm | An inequality of the Hölder type, connected with Stieltjes integration[END_REF] and then generalized variation with a convex function more general than a power law in [START_REF] Chisholm | General inequalities for Stieltjes integrals and the convergence of Fourier series[END_REF]. For the theory of p-variation and generalized variation, we suggest to books [START_REF] Bruneau | Variation totale d'une fonction[END_REF][START_REF] Mansfield | Differentiability of Six Operators on Nonsmooth Functions and p-Variation[END_REF][START_REF] Love | Sur une classe de fonctionnelles linéaires[END_REF] after the article [START_REF] Musielak | On generalized variations[END_REF] build a nice metric structure for generalized variation. The p-variation is mainly used in integration theory and probabilities for a long time [START_REF] Peter | Multidimensional stochastic processes as rough paths[END_REF]. Some applications in probabilities can be found in [START_REF] Mansfield | Concrete functional calculus[END_REF][START_REF] Norvaiša | Rough functions: p-variation, calculus and index estimation[END_REF][START_REF] Qian | The p-variation of partial sum processes and the empirical process[END_REF] mainly supported by Rimas Norvaisa and his collaborators.

PDEs, hyperbolic conservation laws Here, the main motivations of the authors are related to a new subject where the p-variation spaces can be useful. The theory of hyperbolic partial differential equations (PDEs) with nonlinear flux is usually studied in the space BV . Recently the second author and more and more collaborators introduce the fractional BV spaces which are indeed the p-variation spaces [START_REF] Bourdarias | Fractional BV spaces and first applications to scalar conservation laws[END_REF].

It is well known that shock waves appear in finite time even when the initial data is smooth. It is the reason why the BV space of function with bounded total variation is often used. It allows us to consider weak discontinuous solutions with right and left limits everywhere. Moreover, the embedding from BV in L 1 loc is compact. This is fundamental to prove the global existence of weak solutions for such conservation laws. But all weak solutions do not belong to BV . It is the reason why fractional BV spaces, BV s , with 0 < s < 1 has introduced in [START_REF] Bourdarias | Fractional BV spaces and first applications to scalar conservation laws[END_REF] in the context of conservation laws. These spaces have the same properties as BV for the traces and the compactness. These spaces are larger than BV space. The exponent "s" corresponds to the fraction Sobolev derivative and BV 1 = BV . Since 2014 there are more and more applications of these BV s spaces for equations [START_REF] Castelli | Oscillating waves and optimal smoothing effect for one-dimensional nonlinear scalar conservation laws[END_REF][START_REF] Sundar Ghoshal | Optimal regularity for all time for entropy solutions of conservation laws in BV s[END_REF][START_REF] Billel Guelmame | Regularizing effect for conservation laws with a Lipschitz convex flux[END_REF], and for systems of conservation laws [START_REF] Bourdarias | Eulerian and Lagrangian formulations in BV s for gas-solid chromatography[END_REF][START_REF] Bourdarias | Entropy solutions in BV s for a class of triangular systems involving a transport equation[END_REF][START_REF] Junca | Analysis of a Sugimoto model of nonlinear acoustics in an array of Helmholtz resonators[END_REF], existence theory, regularity, and blow-up. All these results are theoretical and the BV s norm is not computed. Now, there is a numerical motivation to look for numerical schemes preserving the fractional BV estimates so to compute the p-variation. Today, only the Godunov scheme [START_REF] Al Zohbi | Entropy solutions to a non-conservative and non-strictly hyperbolic diagonal system inpired by dislocation dynamics[END_REF][START_REF] Bourdarias | Eulerian and Lagrangian formulations in BV s for gas-solid chromatography[END_REF][START_REF] Choudhury | Decay of p-variation for Godunov scheme[END_REF] and some Wave Front Tracking Algorithms [START_REF] Bourdarias | Entropy solutions in BV s for a class of triangular systems involving a transport equation[END_REF][START_REF] Billel Guelmame | Regularizing effect for conservation laws with a Lipschitz convex flux[END_REF][START_REF] Kristian | On ϕ-variation for 1-d scalar conservation laws[END_REF] are already proven to be compatible with the p-variation for scalar conservation laws and some systems.

1 7 3 22 4 25 A

 172225 Examples and properties of optimal sequences . . . . . . . . . . . . . . . . 4 2.2 Main tools to build an optimal subsequence . . . . . . . . . . . . . . . . . Algorithms to compute p-variation 16 3.1 "Eraser" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 "Merge" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3 "AOP"=Add One Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . Efficiency of the algorithms 24 4.1 The cost is at least N 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2 Cost comparisons of the three algorithms . . . . . . . . . . . . . . . . . . . Motivations to compute the p-variation 27 1 Introduction

1 )

 1 -u (i)| p . (1.4)

Figure 1 :Figure 2 :

 12 Figure 1: An oscillating sequence with only two values

H 1 k

 1 is false, p-sum u ≤ |u(1) -u(N )| p and for all strict subsequences v of u we have p-sum v < p-sum u ≤ |u(1) -u(N )| p . Finally for all subsequence v of u, p-sum v ≤ |u(1) -u(N )| p , that means that p-TVu = |u(1) -u(N )| p .

  the existence of b is obtained by the intermediate value theorem. The function g(b) = a p + b p + a p -(2a -b) p = p-sum u -p-sum u * is continuous, g(0) = (2 -2 p )a p < 0 and g(a) = 2a p > 0 so the existence of a positive b < a follows.

Figure 4 :Figure 5 :

 45 Figure 4: ν = 1, case 1.

Figure 6 :Figure 7 :

 67 Figure 6: ν = 1, four case 3.

Figure 8 :

 8 Figure 8: ν = 2, case 1.1 and 1.2 .

Figure 9 :

 9 Figure 9: ν = 2, case 2.1 and 2.2 .

Figure 10 :

 10 Figure 10: ν = 2, case 3.1 and 3.2 .

Figure 11 :

 11 Figure 11: ν = 2, case 4.1 and 4.2.

3 . 6 .

 36 For i= 1 to 2 K do 4. L[i]:=(u(2i-1),u(2i)) 5. End For com conquer sub-sequences two by two For k= 1 to K do

Algorithm 3 :

 3 Add one point (AOP) AOP(u,p) 1. N:=size(u) 2. Start with the list L = (u 1 , u 2 ).

3 .

 3 For n = 3 to N do 4. add the point u n to the list L 5. l = length(L); S = 0 6. for j = 2 to l -1, j = 2 or j odd, do 7. S := S + |u(l + 1 -j) -u(l + 2 -j)| p8.if H ≥ l+1-j,j then9.L := (L(1), . . . , L(l + 1 -j), u(n)) that S is used to test inequality H ≥ l+1-j,j . This test has usually a cost O(j) but with this computation of the sum, it reduces to a cost O(1).

are true, except at most for the subsequences,(L(n -1), L(n), L(n + 1)) = (u(n -1), u(n), v(1)), (L(n), L(n + 1), L(n + 2)) = (u(n), v(1), v(2)).

That means there are only 2 inequalities to check to satisfy H < 2 . If an inequality is not satisfied, then we proceed locally as for eraser, erasing one term and then on the new restart the process to check on the new concatenated chain, without u(n) or v(1) the new two cases to check. When the process is stabilized for j = 2, we continue with j = 3 and so on. Finally at the end, we obtain a sub-sequence of L which is optimal to compute p-TVL. It turns to use this mechanism to build an optimal sequence. Precisely, inequalities H < ij tested have to contain some values of u and v,

The following algorithm merges two optimal sequences in a new optimal one.

Algorithm 2a: Conquer

Conquer(u,v,p) com: u and v are optimal sub-sequences.

1. L := (u, v); n:=size(u); m := size(v); N:=size(L).

2. For j= 2 to N-1, j =2 or j odd do 3.

For i= max(1,n+1-j) to max(n,N-j) do

4.

If H ≥ ij Then u := (L(1), . . . , L(i)), v := (L(i + j), . . . , L(N )); Goto line 1

5.

End If

6.

End For 7. End For

Result:L

The initialization of "Merge" is as follows to compute p-TVu with u = (u(1), . . . , u(N )) We assume that the sequence u has no constant step and to simplify the exposition, that N is a power of 2, N = 2 K+1 , K ≥ 1. The initial sequence is divided in N/2 sequences L[i] = (u(2i -1), u(2i), i = 1, . . . , N/2. These 2 K sequences are optimal since u has no constant step. Now, L [START_REF] Al Zohbi | Entropy solutions to a non-conservative and non-strictly hyperbolic diagonal system inpired by dislocation dynamics[END_REF] and L [START_REF] Bourdarias | Fractional BV spaces and first applications to scalar conservation laws[END_REF] are merged in an optimal sequence with the algorithm "Conquer". The same is done until

]. Now, there are 2 K-1 optimal sequences which are merged two by two again.

The process continues until there are only two optimal sequences left to merge, each with a size between 2 and N/2. The final merging produces an optimal sequence for computing p-TVu.

The algorithm below, named "Merge" performs the splitting into multiple couple sub-sequences. Subsequently, we combine them as previously described until there is just one sub-sequence left for computing p-TVu.

Algorithm 2b: Merge

Merge(u,p) com Split the sequence u into two-point sequences.

com L is the sequence of all these sequences.

1. N:=size(u); K := Log 2 (N ) -1

Efficiency of the algorithms

In this section, the efficiency of the presented algorithms is discussed. All these algorithms has a polynomial costs. The polynomial cost of algorithms is now addressed more precisely.

The cost is at least N 2

Optimal criteria given by Proposition 2.5 has to be used to check that a sequence is optimal one to compute its p-TV by its p-sum , i.e. p-TVu = p-sum u.

Notice that, even if u is an optimal sequence there are many tests to do, indeed O(N 2 ) tests. Moreover the tests involve large sums with at most N terms. So, naively, the cost is at least O(N 3 ). It is possible to reduce the cost of sums because the sum involved in the inequality H < ij , H < (i+1)j have the same terms except the first and the last one:

In this way, testing consecutive inequality H < ij for increasing i does not need the computation of j additions with j < N possibly large, but, only one substraction and one addition [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF]. Managing well the computations of sums as in [START_REF] Li | Efficiency of some algortihms to compute fractal total variation[END_REF] for "AOP" and "Eraser", we can reduce the cost to the number of tests. Thus, O(N 2 ) is the minimal possible cost for any algorithms computing p-TV.

Preprocessing

Since the cost is a power of N , the number of the terms of the sequence, i.e. the length of the sequence, it is useful to reduce the size of the sequence before using one of the algorithms presented. These preprocessings are independent on p, so do not need computations of powers p and large sums.

1. u has no constant step. If u has some constant step, u(i) = u(i + 1) for some i, the sequence is reduced. The following preprocessing has a cost O(N ).

While i < length of u do if u(i) = u(i + 1) then erase the value u(i)

No monotonicity zone. If (u(i -1) -u(i))(u(i) -u(i + 1)) ≥ 0 then, the midle term u(i) is removed without changing p-TVu. This process corresponds to satisfy the condition H 3 without computing the sum and the three p-powers to check inequality H < i2 . It means that if three consecutive terms are in monotinc order, the midle term is removed. Again, The following preprocessing has a cost O(N ).