Keywords: Collaborative filtering, Content-based filtering, Fuzzy clustering, Hybrid recommender system

Recommender systems provide relevant items to users from a large number of choices. In this work, we are interested in personalized recommender systems where user model is based on an analysis of usage. Collaborative filtering and content-based filtering are the most widely used techniques in personalized recommender systems. Each technique has its drawbacks, so hybrid solutions, combining the two techniques, have emerged to overcome their disadvantages and benefit from their strengths. In this paper, we propose a hybrid solution combining collaborative filtering and content-based filtering. With this aim, we have defined a new user model, called userfeature model, to model user preferences based on items' features and user ratings. The user-feature model is built from the user item model by using a fuzzy clustering algorithm: the Fuzzy C Mean (FCM) algorithm. Then, we used the user-feature model in a user-based collaborative filtering algorithm to calculate the similarity between users. Applying our approach to the MoviesLens dataset, significant improvement can be noticed comparatively to the main CF algorithm, denoted as user-based collaborative filtering.

I. INTRODUCTION

Recommender systems provide relevant items to users from a large number of choices. Several recommendations techniques exist in the literature [START_REF] Burke | Hybrid Recommender Systems: Survey and Experiments[END_REF]. Among these techniques, there are those that provide personalized recommendations by defining a profile for each user. In this work, we are interested in personalized recommender systems where the user model is based on an analysis of usage. This model is usually represented by a user-item rating matrix, which is extremely sparse (> 90% of missing data).

Collaborative filtering (CF) has been the first personalized recommender system [START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF]. In collaborative filtering, user will be recommended items that people with similar tastes and preferences liked in the past. Content-based filtering (CB) is another important technique, of recommender systems, it assumes that each user operate independently. In contentbased recommender systems, user will be recommended items similar to the ones he preferred in the past. Content-based filtering uses techniques developed in information retrieval and, information filtering research. The major difference between CF and content-based recommender systems is that CF only uses the user-item ratings data to make predictions and recommendations, while content-based recommender systems rely on the features of items for predictions.

However, each technique introduces some shortcomings. In CF techniques, if a new item appears in the database, there is no way to be recommended before it is rated, this problem is known as Cold-start [START_REF] Adomavicius | Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions[END_REF]. Neighbor transitivity [START_REF] Su | A survey of collaborative filtering techniques[END_REF] refers to a problem with sparse databases, in which users with similar tastes may not be identified as such if they have any items rated in common. On the other hand, if a user's taste is unusual, he cannot find neighbors, and gets inaccurate recommendations, this problem is known as Gray Sheep [START_REF] Su | A survey of collaborative filtering techniques[END_REF]. Content-based filtering suffers a problem of overspecialization where a user is restricted to seeing items similar to those already rated.

To overcome the disadvantages of both techniques and benefit from their strengths, hybrid solutions have emerged. Most of these hybrid systems are process-oriented: they run CF on the results of CB or vice versa. CF exploits information from the users and their ratings [START_REF] Adomavicius | Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions[END_REF]. CB exploits information from items and their features. However, they miss the relation between, user ratings and items' features. This link may explain the user interests for an item.

In this paper, we propose a hybrid solution combining collaborative filtering and content-based filtering. Our solution defines a new user model, user-feature model, to model user preferences based on items content. Therefore, our user model is the link between the user ratings and the items' features and defines user-features preferences.

The user-feature model is built from the user-item model by using a fuzzy clustering algorithm: the Fuzzy C Mean (FCM) algorithm [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF].

We used the user-feature model in a user-based CF algorithm [START_REF] Su | A survey of collaborative filtering techniques[END_REF] to calculate the similarity between users. We compared our results to the main CF algorithm, denoted as user-based CF (UB) [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF]. The results obtained demonstrate the superiority of the proposed approach.

Our contribution is summarized as follows: (i) We construct a novel user-feature model, representing the link between user's preferences and item's features, (ii) We use a fuzzy clustering algorithm, FCM, for the construction of this model, (iii) We provide predictions and recommendations by using Sonia Ben Ticha , Azim Roussanaly, Anne Boyer, Khaled Bsaïes E-mails: Sonia.benticha@ensi.rnu.tn, azim.roussanaly@loria.fr, anne.boyer@loria.fr, khaled.bsaies@fst.rnu.tn

User-Feature Model for Hybrid Recommender System

the user-feature model, in a user-based CF algorithm, for computing similarity between users, (iv) We perform several experiments with MoviesLens data sets, which showed improvement in the quality of predictions compared to userbased CF. The rest of the paper is organized as follows: section 2 summarizes the related work. The proposed approach is described in Section 3. Experimental results are given in Section 4. Finally, Section 5 concludes this paper.

II. RELATED WORK

Recommender systems have become an independent research area in the middle 1990s after the apparition of the first paper on personalized recommender systems based on collaborative filtering [START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF]. Collaborative filtering is the most widespread used technique in recommender systems. It was the subject of several researches [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF], [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative filtering[END_REF], [START_REF] Sarwar | Item-based collaborative filtering recommendation algorithms[END_REF], [START_REF] Aggarwal | Horting Hatches an Egg: A New Graph-Theoretic Approach to Collaborative Filtering[END_REF].

Purely content-based recommender systems are less widespread. Techniques used are from information retrieval and information filtering research. Notable works can be find in Pazzani [START_REF] Pazzani | Learning and Revising User Profiles:The Identification of Interesting Web Sites[END_REF] and Ferman [START_REF] Ferman | Content-based filtering and personalization using structured metadata[END_REF].

The Fab System of Balabanovic [START_REF] Balabanovic | Fab: "Content-Based, Collaborative Recommendation[END_REF] counts among the first hybrid recommender systems. Several other systems have been developed since [START_REF] Billsus | A Personal News Agent that Talks, Learns and Explains[END_REF], [START_REF] Melville | Content-Boosted Collaborative Filtering for Improved Recommendations[END_REF], [START_REF] Soboroff | Combining Content and Collaboration in Text Filtering[END_REF]. Most of these hybrid systems are process-oriented: they run CF on the results of CB or vice versa. In [START_REF] Mobasher | Semantically enhanced collaborative filtering on the web[END_REF], authors integrate semantic similarities for items with user-rating similarities. The combined similarity measure was used in an item-based CF to generate recommendations. These works ignore the dependency between user-ratings and items' features. Taking account of the link between them can improve the quality of recommendation. In [START_REF] Symeonidis | Feature-Weighted User Model for Recommender Systems[END_REF], this dependency was computed using the term frequency/inverse document frequency (TF-IDF) measure that is the best-known measures for specifying keyword weights in Information Retrieval. The authors use this measure to calculate the weight of feature for each user. In our approach, we used a fuzzy clustering algorithm, Fuzzy C Mean, to compute the estimated user-rating for each feature. The result of the Fuzzy C Mean algorithm is used to provide a new user profile based on the items' features. Thus, users are modeled by the user-feature model that defined the dependency between user rating and items' features (semantic of items).

III. PROPOSED APPROACH

A. Notations

In this section, we provide details about the used terminology. Table I, summarizes the symbols used in this paper.

-The user profile is defined by a rating vector: U u =(r u,1 ,r u,2 ,…,r u,i, …,r u,m ) -The item profile is defined by: o a rating vector: I i =(r 1,i ,r 2,i ,…r u,i ,…,r N,i ) o an item-features vector:

F i =(b i,1 ,b i,2 ,…,b i,D )
where:

𝑏 𝑖,𝑓 = 0 𝑖𝑓 𝑖𝑡𝑒𝑚 𝑖 ℎ𝑎𝑠𝑛 ′ 𝑡 𝑓𝑒𝑎𝑡𝑢𝑟𝑒 𝑓 1 𝑖𝑓 𝑖𝑡𝑒𝑚 𝑖 ℎ𝑎𝑠 𝑓𝑒𝑎𝑡𝑢𝑟𝑒 𝑓 B.
Architecture We propose a system that takes into account the dependence between user's ratings and items' features. This dependency is represented by the user-feature matrix.

The aim of this study is to know whether the fact of taking into account the relationship between user's ratings and the features of items, in the recommender process, can improve the relevance of the recommended items.

The outline of our methodology consists of 2 steps as shown in Fig. 1: 1. The user-feature matrix construction step: by using a fuzzy clustering algorithm: the Fuzzy C-Mean [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF] we build a user-feature profile from the item-user ratings matrix I and the item-feature matrix F. Obviously, for achievement reasons, this processing can be offline. 2. The recommendation step: we provide for each user a recommendation list of relevant items based on the user-based CF algorithm [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF]. The similarity between two users is computed, in our algorithm, by using the user-feature matrix instead of the user-item rating matrix.

In the following sections, we describe each step in detail.

C. Construction of user-feature matrix

The user-feature matrix A(N lines and L columns), describes the user-feature profile for each user. The userfeature profile provides preferences of user u for all features from his preferences for items. It is defined by the vector A u =(a u,1 ,…,a u,f ,a u,L ). L is the number of features, a u,f indicates the preference of user u for feature f and will be computed by our algorithm.

In this section we describe in detail the steps of the construction of the user-feature model defined by the userfeature matrix A.

For building the matrix A, our algorithm computes before the transposed matrix A t of A. The vector

A t f =(a 1,f ,a 2,f ,…,a u,f ,…a N,f
) is the profile of a feature f computed from the users' ratings. This profile can be performed by a generalization model like a partitioning method.

Then, the clustering algorithm classifies the set of items by features, so that, items within cluster have high similarity compared to their features. Thus, the center of each cluster defines the profile of the corresponding feature and is modeled by the vector A t f .

Since an item belongs to several features, we need to use a fuzzy clustering algorithm. In literature there are many fuzzy clustering algorithms. Initially, we choose the Fuzzy C Mean (FCM) algorithm [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF]. In future works, we will test other algorithms and will compare the different results. FCM algorithm is very similar to the k-mean algorithm, but it provides non-disjointed clusters.

The construction of user-feature matrix consists of 2 steps as shown in Fig 2: 1. Performing of the features profiles by using the Fuzzy C Mean algorithm. This step provides L non-disjoint clusters represented by their centroid C k , k  [1,L] and, for each item i a coefficient, p k,i , giving the degree of membership of item I i to cluster k. 2. Computing of the transposed matrix of C: C is an LxN dimension matrix; each line defined the profile of the corresponding feature. The transposed of C gives the

                    L N L i L k N k i i N L k N i a a a a a a a a C C C u u u , , , 1 , , , 1 1

List of revelant items for active user active user Recommendation

matrix A that is the user-feature matrix. A gives for each user u his features' preferences.

In the followings sections we present in details the FCM algorithm and its initialization step.

Fuzzy C Mean Algorithm (FCM)

The FCM algorithm is one of the most widely used fuzzy clustering algorithms. This technique was originally introduced by Jim Bezdek in 1981 [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF]. The FCM algorithm attempts to partition a finite collection of elements E={X 1 ,X 2 ,…,X M } into a collection of L fuzzy clusters with respect to some given criterion. Given a finite set of data, the algorithm returns -a list of L cluster centers C k such that C k =v i ,i=1,…,N -a partition matrix P such that: P=p ij , i=1,…,L and j=1,….,M, p ij is a coefficient [0,1] giving the degree to which the element X j belongs to the i-th cluster. Usually, the sum of those coefficients for any given element X is defined to be 1 as shown in equation ( 1).



 . 1 p X 1 x k,     clusters nb k (1)
The center of a cluster is the mean of all elements, weighted by their degree of belonging to the cluster (equation ( 2

)). . , ,    X m X k X m x k k p X p C (2)
The coefficient of belonging is related to the inverse of the distance to the cluster center. In equation (3) the coefficients are normalized and fuzzyfied with a real parameter m>1 so their sum is 1.

           j m j k k,x X C distance X C distance p ) 1 /( 2 ) , ( ) , ( 1 (3)
The FCM algorithm consists of the followings steps: -Choose a number of clusters, -Assign to each element coefficients of belonging to the clusters, -Repeat until the algorithm has converged: * Compute the center for each cluster, using the formula gives by equation ( 2) * For each element, computes its coefficients for being in the clusters, using the formula gives by equation ( 3).

In our algorithm the collection of elements is the items, X is replaced by I i and the number of clusters is L.

Foe the distance measure, we use the Manhattan distance given by the formula of the equation [START_REF] Billsus | A Personal News Agent that Talks, Learns and Explains[END_REF] .

1        n i i i i y x Y X Y) (X, distance (4)
Where X and Y is two vectors in an n-dimensional real vector space.

The number of clusters

In most clustering methods, we must study the number of clusters to choose. Indeed, the results of some techniques could be influenced by this number. In our case, this problem does not arise; the number of clusters is equal to the number of features. Our aim is to provide a profile for each feature based on users ratings. This profile is given by the cluster centroid.

Initialization of the Fuzzy C Mean Algorithm

Like the K-mean algorithm, the FCM algorithm needs an initialization of the partition matrix or the clusters centers.

In our algorithm, we initialize the partition matrix with respect to the formula given in equation ( 1).We use, for that, the item-feature matrix F, then the degree to which the item i belongs to a cluster k is given by the equation ( 5)

           0 0, 1 , 1 , 1 , , k k i,f f i L f f i i k if b b if b p (5)
Example:

f 1 f 2 f 3 i 1 0 1 1 i 2 1 0 1 i 3 1 1 1 i 4 1 1 0
In this example, we have three clusters. p 3,4 =0 because b 4,3 =0, that means item 4 hasn't feature 3, and p 2,4 =0.5 and p 1,4 =0.5 then, p 1,4 +p 2,4 +p 3,4 =1. We assume that all the features of an item have the same weight. This assumption can be changed if we have the information about the importance of each feature in an item.

D. Recommendation

For the recommendation process we use the user-based CF [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF] algorithm that is a memory based algorithm. Memorybased CF algorithms use the entire or a sample of the useritem matrix to generate predictions. Every user is part of a group of people with similar interests. By identifying the socalled neighbors of the active user, predictions on new items for him or her can be produced.

The used-based CF algorithm, a prevalent memory-based CF algorithm, based on the KNN algorithm (K Nearest Neighborhood) consists of the following steps:

-Calculate the similarity w u,v : which reflects the correlation between the two users u and v. The similarity is computed by the Pearson correlation introduced by Resnick et al. [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF]. -Compute the predictions: produce predictions is the most important step in a collaborative filtering system. In the user-based CF algorithm, a subset of nearest neighbors of the active user are chosen based on their similarity with him or her, and a weighted aggregate of their ratings is used to generate predictions for the active user. -Recommendation: the system recommends to the active user, the items with predicted ratings greater than a given threshold.

Equation ( 6) gives the Pearson correlation, formula that used in user-based CF algorithm.

         i v vi i u ui i v vi u ui v u r r r r r r r r w v u sim 2 2 , ) ( ) ( ) )( ( ) , ( (6)
Where the i summations are over the items that both the users u and v have rated and ru is the average rating of the rated items of the user u.

In user-based CF algorithm, the user-item matrix is used to compute user similarities. In our algorithm, we use the featureuser matrix instead. This allows inferring similarity between two users even when they have any co-rated items. Thus, our approach provides solution to the neighbor transitivity problem emanates from the sparse nature of the underlying datasets. In this problem, users with similar preferences may not be identifies as such if they haven't any items rated in common.

Furthermore, Pearson correlation is the most widely used measure in user-based CF research. That is why we chose for computing users similarities. In addition, we will be able to compare our results with those of the user-bases CF algorithm described in [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF].

We use the equation [START_REF] Ferman | Content-based filtering and personalization using structured metadata[END_REF] to calculate the similarity between users instead of the formula of equation [START_REF] Burke | Hybrid Recommender Systems: Survey and Experiments[END_REF].

         f v vf f u f f v vf u uf v u a a a a a a a a w v u sim 2 2 , ) ( ) ( ) )( ( ) , ( (7)
Where the f summations are over the features that users u and v have both a value, and au is the average of a u,f ., f=1,…,L For computing the prediction, pr u,i , for user u on non-rated item i, we used formula of equation ( 8).

) , ( 1)

)( , ( r u ,         V v V v v vi i u v u sim k where r r v u sim k pr (8)
V denotes the set of H users that are the most similar to user u and who have rated item i (H can range anywhere from 1 to the number of all users). Sim(u,v) is calculated in our algorithm by using formula of equation ( 7). That's mean; we use the user-feature matrix for computing the correlation between users.

The outline of our user-based CF consists of the following steps:

-Computing similarities between users, by using the userfeature matrix -Computing predictions for active user by using the formula of equation ( 8)

-Recommend items that predicted rating is greater than a given threshold.

IV. PERFORMANCE STUDY

In this section, we study the performance of our model named Fuzzy user-feature CF against the simple CF algorithm, denoted as user-based CF (UB) described in [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF]. We have implemented all these methods in Java. We evaluate these techniques in terms of relevancy of predictions.

A. The used corpus and experiments

In order to compute the prediction relevancy in our system, we used the GroupLens [START_REF] Movielens | [END_REF] dataset. The latter is composed of 100.000 ratings of real users, 943 users, 1682 items and 19 features. Items are movies, and features are the movie's genres. A same film may have several genres, for example, the movie "Toy Story" has three genres: Animation, Children's and Comedy. Moreover, each user has rated at least 20 items.

The dataset has been divided into a training set (including 80% of all ratings) and a test set (20% of votes). We use the For the first step of our algorithm, user-feature model construction (see Fig 1), the data has been cleaned up, items that have less than 5 ratings, are removed from the dataset. Then, after the cleaning step, we have retained 1348 items and 18 genres.

We have executed the FCM algorithm for different values of the fuzzy parameter m. The number of iterations was set at 500. For the most values of m, the FCM has converged expect for m=1,25.

B. Results

We compare our algorithm with the user-based CF described in [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF] by using the Mean Absolute Error (MAE) [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF] and the Root Mean Squared Error (RMSE).

MAE is the most widely used metric in CF research literature, which computes the average of the absolute difference between the predictions and true ratings, as shown in equation [START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF]

. d r pr MAE i u i u i u    , , , (9)
Where d is the total number of ratings over all users, p u,i is the predicted rating for user u on item i, and ru, i is the actual rating. Lower the MAE is, better is the prediction. We can conclude that the fact of taking account the features of item in the recommendation process improve the quality of recommendation. This can be explained by the fact that our approach allows inferring similarity between two given users even when they have any items rated in common, since we use the user-feature matrix instead of the user-item rating matrix for computing similarity in the recommendation process.

RMSE is becoming popular partly because it is the

V. CONCLUSION AND FUTURES WORKS

In this paper, we have proposed a hybrid solution combining collaborative filtering and content-based techniques. The contribution of our solution over the solutions proposed in the literature is the identification of the link between user ratings and items' features. This link was defined by the user-feature model that modeled the userfeature preferences. The user-feature model, allows inferring similarity between two given users, even when they have any items rated in common. Thus, our approach provides solution for the Neighbor transitivity problem, in which users with similar tastes may not be identified, if they have not both rated any of the same items. Besides, our solution alleviates the data sparsity problem by reducing the dimensionality of data. In fact, the number of features is less than the number of items, so the user feature matrix dimension is smaller than the useritem ratings matrix dimension.

The results obtained are encouraging; they demonstrate the superiority of the proposed approach compared to the main CF algorithm: user-based CF [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF].

As futures works, we will apply our approach to multicriteria items. For example in the case of the MovieLens data sets, in addition to the genre, one can add the main actors in films. Otherwise, we will apply others Data Mining algorithms to construct the user-feature model.

Fig. 2 .

 2 Fig. 2. The fuzzy clustering algorithm provides L non-disjoint clusters. Ck is the centroid of the cluster k, Ck is a generalized profile of the feature fk, defined in N dimensional space. Ck=A t k

  . ..... ...... ..... ........ ..

Fig. 1

 1 Fig.1Architecture of the hybrid recommender system using the item's features: the Fuzzy user-feature CF

Fig 3 .

 3 Fig 3. Comparison of prediction quality using the MAE between our algorithm and the used-based CF

  Netflix prize [13] metric for movie recommendation performance: RMSE amplifies the contributions of the absolute errors between the predictions and the true values. Table II and Fig 3 demonstrate that our algorithm compares favorably against user-based CF for small values of m. The reason is when m is close to 1, then the cluster center closest to the items is given much more weight than the others and the FCM is similar to K-means. For large values of m, the Fuzzy user-feature CF converge and the MAE remain unchanged as shown in Fig 4.

Fig 4 .

 4 Fig 4. MAE of Fuzzy user-Feature against the fuzzy parameter m

  ...... .......... .......... .......... ..........

	I	:	the					item		-	user	ratings	matrix
		.....	?	....		?	.......	??	...	?	.......	?	...	?	...
	....		...	?	..	?	.....	?	...	?	...	?	....	?	.....	?	....	?
	?			..	?	....	??	.......	....	?	..	?	..	?	...
	?					......	?	..	?	..	?	......	?	..	?	.....	?
	?		...	?	...	?	....	?	....	?	....	?	....	?	......	?
				.....	?	.....	?	.....	......	?	..	?	..

.

  ...... .......... .......... .......... ..........

	I	:	the				item			-	user	ratings	matrix
		.....	?	....	?	.......	??	...	?	.......	?	...	?	...
	....	...	?	..	?	.....	?	...	?	...	?	....	?	.....	?	....	?
	?			..	?	....	??	.......	....	?	..	?	..	?	...
	?					......	?	..	?	..	?	......	?	..	?	.....	?
	?		...	?	...	?	....	?	....	?	....	?	....	?	......	?
			.....	?	.....	?	.....	......	?	..	?	..

.


Damien Jamet
email: jamet@loria.fr

Jean-Luc Toutant
email: toutant@lirmm.fr

On the Connectedness of Rational Arithmetic Discrete Hyperplanes

While connected arithmetic discrete lines are entirely characterized by their arithmetic thickness, only partial results exist for arithmetic discrete hyperplanes in any dimension. In the present paper, we focus on 0-connected rational arithmetic discrete planes in Z 3 . Thanks to an arithmetic reduction on a given integer vector n, we provide an algorithm which computes the thickness of the thinnest 0-connected arithmetic plane with normal vector n.

Introduction

In [START_REF] Reveillès | Géométrie discrète, Calcul en Nombres Entiers et Algorithmique[END_REF], J.-P. Reveillès initiated a new approach of linear discrete objets and introduced arithmetic discrete lines as sets of pairs of integers satisfying a double Diophantine inequality : the arithmetic discrete line with normal vector n ∈ R 2 , translation parameter µ ∈ R and thickness w ∈ R is the set D(n, µ, w) = x ∈ Z 2 , 0 ≤ n • x + µ < w , where n • x = n 1 x 1 + n 2 x 2 is the usual Euclidean scalar product of n and x. Geometrically, an arithmetic discrete line can be viewed as a set of integer points of the plane R 2 included in a band delimited by two parallel Euclidean lines (see Fig. 1). The thickness parameter w plays a key role in the topology of the arithmetic discrete lines: given n ∈ R 2 and µ ∈ R, the thinnest 0-connected (resp. 1-connected) arithmetic discrete line among the ones with normal vector n and translation parameter µ is the arithmetic discrete line D(n, µ, n ∞ ) (resp. D(n, µ, n 1 )) (see Section 2 for the definition of the 0-connectedness and 1-connectedness) [START_REF] Reveillès | Géométrie discrète, Calcul en Nombres Entiers et Algorithmique[END_REF].

The definition of arithmetic discrete lines extends naturally in dimension 3 to the arithmetic discrete planes and in any dimension d ≥ 2 to the arithmetic discrete hyperplanes [START_REF] Andres | Discrete analytical hyperplanes[END_REF]. It is thus natural to try to exhibit a similar relation between the κ-connectedness of an arithmetic discrete hyperplane and its thickness. In fact, the 2-dimensional case is somewhat confusing since a 0-connected (resp. 1connected) arithmetic discrete line is also 1-separating (resp. 1-separating) in Z 2 (see Section 2). In the particular case of rational arithmetic discrete hyperplanes (remember that an arithmetic discrete hyperplane is rational if its normal vector n ∈ R d is colinear to an integer vector, or equivalently, if the Q-vector space spanned by {n 1 , . . . , n d } is of dimension 1), several approaches have been attempted [START_REF] Andres | Discrete analytical hyperplanes[END_REF][START_REF] Gérard | Periodic graphs and connectivity of the rational digital hyperplanes[END_REF][START_REF] Brimkov | Connectivity of discrete planes[END_REF] although none of them provides an explicit formula to compute the thickness of the thinnest 0-connected rational arithmetic discrete hyperplane with any given normal vector.

In [START_REF] Brimkov | Connectivity of discrete planes[END_REF], V. Brimkov and R. Barneva partially solved this request for rational arithmetic discrete planes whose the normal vector n ∈ Z 2 satisfies particular conditions (for instance when |n 1 | + 2|n 2 | ≤ |n 3 |) and provided an algorithm for the entire problem. Unfortunately, their algorithm seems to incorrect and does not generally return the right thickness (see Section 4).

In [START_REF] Gérard | Periodic graphs and connectivity of the rational digital hyperplanes[END_REF], Y. Gérard investigated a problem close to the one we are interested in in the present paper: given an arithmetic discrete hyperplane P(n, µ, w) and κ ∈ {0, . . . , d -1}, is P(n, µ, w) κ-connected ? In other words, given the graph G(n, µ, w) whose vertices are the points of P(n, µ, w) and whose edges are the pairs {x, y} of κ-adjacent points of P(n, µ, w), does G(n, µ, w) admit a unique connected component ? The main difficulty of this problem is the possibly infiniteness of G(n, µ, w). Assuming dim Q {n 1 , . . . , n d } = 1, one reduces G(n, µ, w) to a finite graph by quotienting G(n, µ, w) iteratively by a subgroup of rank 1 of the lattice of periods of P(n, µ, w). Since G(n, µ, w) is injectively projectable in Z d , then, with at most d such quotienting processes, one reduces G(n, µ, w) to a finite graph with the same connectedness as G(n, µ, w).

In the present paper, we deal with the determination of the thickness of the thinnest 0-connected rational arithmetic discrete plane with a given normal vector n. For this purpose, we give a short and elementary algorithm which takes a vector n ∈ Z 3 as entry and returns the thickness w of the thinnest 0-connected arithmetic discrete plane with normal vector n. While Y. Gérard, V. Brimkov and R. Barneva's approaches need to determine a connected component, our algorithm is entirely arithmetic and does not need to consider any connectivity graph.

Here is the sketch of the present paper. Section 2 is devoted to the basic notions useful for the remaining. In Section 3, we investigate the notions of κ-connectedness and κ-separatingness and state a first comparison between their characterization in the case of rational arithmetic discrete lines and rational arithmetic discrete hyperplanes. In Section 4, we focus on V. Brimkov and R. Barneva's investigation [START_REF] Brimkov | Connectivity of discrete planes[END_REF]. After having recalled some of their results, we exhibit a counter example of the algorithm they proposed. In Section 5, we introduce an arithmetic reduction on the integer vectors preserving the 0connectedness of arithmetic discrete planes. We end this section by designing an elementary and quite short algorithm which computes the minimal thickness by iterating this arithmetic reduction.

Basic Notions

The aim of this section is to introduce the basic notions and definitions we use throughout the present paper.

Let d be an integer equal or greater than 2 and let {e 1 , . . . , e d } denote the canonical basis of the Euclidean vector space R d . Let us call a discrete set any subset of the discrete space Z d . In the following, for the sake of clarity, we denote by (x 1 , . . . , x d ) the point (resp. vector)

x = d i=1 x i e i ∈ R d . An integer point x ∈ Z d is called a voxel (resp. a pixel if d = 2). A subset of Z d is called a discrete set. Let κ ∈ {0, . . . , d -1}. Two voxels x ∈ Z d and x ′ ∈ Z d are said to be κ- adjacent if x -x ′ ∞ = 1 and x -x ′ 1 ≤ d -κ.
In other words, x ∈ Z d and x ′ ∈ Z d are κ-adjacent if they are distinct, the differences of their coordinates are at most 1 and x and x ′ have at most d-κ different coordinates (resp. at least κ identical components). A κ-path is a (finite or infinite) sequence of consecutive κ-adjacent voxels. If (γ i ) 1≤i≤n is a finite κ-path, then we say that γ links the voxel γ 1 to the voxel γ n . A subset E ⊆ Z d is said κ-connected if, for each pair of voxels (x, x ′ ) ∈ E 2 , there exists a κ-path in E linking x to x ′ . Given a discrete set E ⊆ Z d and given κ ∈ {0, . . . , d -1}, one says that E is κ-separating in Z d if its complement in Z d has (at least) two κ-connected components.

In [START_REF] Reveillès | Géométrie discrète, Calcul en Nombres Entiers et Algorithmique[END_REF], J.-P. Reveillès introduced the arithmetic discrete line as a set of integer points satisfying a double Diophantine inequality. This definition extends in a natural way to higher dimensions: Definition 1 (Arithmetic discrete hyperplane [START_REF] Reveillès | Géométrie discrète, Calcul en Nombres Entiers et Algorithmique[END_REF][START_REF] Andres | Discrete analytical hyperplanes[END_REF]). The arithmetic discrete hyperplane with normal vector n ∈ Z d , translation parameter µ ∈ Z and thickness w ∈ Z is the discrete set P(n, µ, w) defined by:

P(n, µ, w) = x ∈ Z d , 0 ≤ n • x + µ < w , (1)
where n • x denotes the usual Euclidean scalar product in Remark 1. Throughout the present paper, when P(n, µ, w) is a rational arithmetic hyperplane, we assume, with no loss of generality, that gcd{n 1 , . . . , n d } = 1, µ ∈ Z and w ∈ Z. Moreover, since the isometry group of the unit cube [-0.5, 0.5] d acts on the set of arithmetic discrete hyperplanes and since any isometry of [-0.5, 0.5] d preserves the κ-connectedness of any arithmetic discrete hyperplane, whatever κ ∈ {0, . . . , d -1}, then in the following, except when explicitly mentioned, we suppose the normal vector n ∈ Z d to satisfy 0

R d . If w = n ∞ (resp. w = n 1 ) then P(n, µ, w) is said naive (resp. standard). If d =
≤ n 1 ≤ • • • ≤ n d .
In Section 3, we recall some partial results on the connectedness of arithmetic discrete lines and give a first extension of them to arithmetic discrete hyperplanes.

3 κ-Connected Arithmetic Discrete Lines vs.

κ-Separating Arithmetic Discrete Hyperplanes

Let us first deal with the case d = 2. In [START_REF] Reveillès | Géométrie discrète, Calcul en Nombres Entiers et Algorithmique[END_REF], J.-P. Reveillès showed how the κ-connectedness of an arithmetic discrete line depends only on its normal vector and its thickness:

Theorem 1 ([1]
). Let D(n, µ, w) be the arithmetic discrete line with normal vector n ∈ Z 2 , translation parameter µ ∈ Z and thickness w ∈ Z.

Then D(n, µ, w) is 0-connected (resp. 1-connected) if and only if w ≥ n ∞ (resp. w ≥ n 1 ).
It becomes natural to try to extend Theorem 1 to higher dimensions, that is, given n ∈ Z d , µ ∈ Z and κ ∈ {0, . . . , d -1}, to try to characterize the thickness of the thinnest κ-connected arithmetic discrete hyperplane with normal vector n and translation parameter µ.

Let us give a helpful reduction of our problem: if µ ∈ Z and n ∈ Z d , then the κ-connectedness (resp. κ-separatingness in Z d ) of P(n, µ, w), whatever d ≥ 2 and κ ∈ {0, . . . , d -1}, does not depend on the translation parameter µ. Indeed, it is a direct consequence of the following lemma: Lemma 1. Let P(n, µ, w) be an arithmetic discrete hyperplane with d ≥ 2, µ ∈ Z and n ∈ Z d . For all µ ′ ∈ Z, there exists a vector α ∈ Z d such that P(n, µ, w) = P(n, µ ′ , w) + α.

Proof. It obviously follows form Bezout's Lemma applied on the coordinates of n.

⊓ ⊔

From now on, we consider only rational arithmetic discrete hyperplanes with a null translation parameter. Thanks to Lemma 1, in the determination of the thickness of the thinnest arithmetical discrete hyperplane with a given rational normal vector, this assumption is not restrictive. From now on, in order to simplify the notation, we denote by P(n, w) the arithmetic discrete hyperplane with normal vector n, translation parameter 0 and thickness w. Let us now investigate the κ-connectedness of arithmetic discrete planes (d = 3). It is not difficult to exhibit a 0-connected arithmetic discrete plane P(n, w) thinner than the naive one, that is, satisfying w < n ∞ (see Fig. 2). Similarly, one easily finds a 2-connected arithmetic discrete plane P(n, w) thinner than the standard one, that is, with w < n 1 . In other words, ]x[ κ is equal to the sum of the (κ + 1) greatest absolute values of the coordinates of x.

One checks that, for each κ ∈ {0, . . . , d -1}, the map ]

• [ κ : R d -→ R d is a norm on R d . Moreover, one has ] • [ 0 = • ∞ and ] • [ d-1 = • 1 .
In the particular case of d = 2, for κ ∈ {0, 1}, the κ-connected arithmetic discrete lines are exactly the (2 -(κ + 1))-separating ones in Z 2 and Theorem 1 is reformulated as follows:

Theorem 2 ( [START_REF] Reveillès | Géométrie discrète, Calcul en Nombres Entiers et Algorithmique[END_REF]). Let D(n, w) be the arithmetic discrete line with normal vector n ∈ Z 2 and thickness w ∈ Z. Let κ ∈ {0, 1}. Then, D(n, w) is (1κ)separating in Z 2 if and only if w ≥ ]n[ κ .

In fact, as previously mentioned, the κ-separatingness of an arithmetic discrete hyperplane P(n, w), whatever the dimension d, is entirely characterized by ]n[ κ . Indeed, Theorem 2 extends in the most natural way to every dimension:

V. Brimkov and R. Barneva's Investigation : an

Algorithmic Approach [START_REF] Brimkov | Connectivity of discrete planes[END_REF] In [START_REF] Brimkov | Connectivity of discrete planes[END_REF], V. Brimkov and R. Barneva investigated 0-connected rational arithmetic discrete planes. They explicitly provided the 0-connecting thickness of some vectors n ∈ Z 3 and an algorithm for computing it in the general case. In the present section, we exhibit a counter-example to this algorithm and deduce that it does not always return the correct output. Let P(n, w) be a rational arithmetic discrete plane. It is well known that if w ≥ n ∞ then P(n, w) is 0-connected (see [START_REF] Andres | Discrete analytical hyperplanes[END_REF] Cor. 10 p. 307). Hence, if w 0 is the 0-connecting thickness of n, then w 0 ≤ n ∞ . In [START_REF] Brimkov | Connectivity of discrete planes[END_REF], V. Brimkov and R. Barneva reduced the determination of w 0 to the determination of the 0-connectedness of a subset of Z 2 as follows: Theorem 4 ( [START_REF] Brimkov | Connectivity of discrete planes[END_REF]). Let P(n, w) be a rational arithmetic discrete plane with n ∞ = |v 3 | and w ≤ n ∞ . The arithmetic dscrete plane P(n, w) is 0-connected in Z 3 if and only if the set {x ∈ Z For the sake of clarity, we introduce the following notation: Notation. -Let P(n, w) be an arithmetic discrete plane with n ∞ = |v 3 | and w ≤ n ∞ . We denote by Π(n, w)

2 , v 1 x 1 + v 2 x 2 mod v 3 ∈ [0, w[} is 0-connected in Z 2 .
the set {x ∈ Z 2 , v 1 x 1 +v 2 x 2 mod v 3 ∈ [0, w[}.
In what follows, since Π(n, w) can be indexed by (a subset of) Z 2 , we call Π(n, w) the array of remainders of P(n, w). For x ∈ Z 2 , the number v 1 x 1 +v 2 x 2 mod v 3 is called the remainder of x. Let us notice that this denomination is not exactly the one used in [START_REF] Brimkov | Connectivity of discrete planes[END_REF][START_REF] Debled-Rennesson | Etude et reconnaissance des droites et plans discrets[END_REF], but is equivalent in the way we use it.

With this notation, from Theorem 4, it follows:

Corollary 1. Let P(n, w) be a rational arithmetic discrete plane with n ∞ = |v 3 | and w ≤ n ∞ . The arithmetic dscrete plane P(n, w) is 0-connected in Z 3 if and only if the set

Z 2 \ Π(n, w) is not 0-separating in Z 2 .
Before describing V. Brimkov and R. Barneva's algorithm, let us introduce a notation: Notation. -Let n ∈ Z 3 such that 0 ≤ n 1 ≤ n 2 ≤ n 3 and gcd{n 1 , n 2 , n 3 } = 1. We denote by Γ(n) the set of 1-paths in Π(n, n ∞ ) linking two points of maximal remainder, that is, n 3 -1. For a 1-path γ ∈ Γ(n), we denote by

min(γ) = min{n 1 i 1 + n 2 i 2 mod n 3 , (i 1 , i 2 ) ∈ γ}.
In other words, min(γ) is the smallest remainder reached in γ.

In [START_REF] Brimkov | Connectivity of discrete planes[END_REF], V. Brimkov and R. Barneva stated:

Theorem 5 ([4]). Let n ∈ Z 3 such that 0 ≤ n 1 ≤ n 2 ≤ n 3 and gcd{n 1 , n 2 , n 3 } = 1. Let w 0 ∈ Z be the 0-connecting thickness of n. Then w 0 = max {min(γ) ∈ Γ (n)} + 1.
Given a vector n ∈ Z 3 satisfying 0 ≤ n 1 ≤ n 2 ≤ n 3 and gcd{n 1 , n 2 , n 3 } = 1, the problem of determining w 0 can thus be reduced to the following one: how to compute max {min(γ) ∈ Γ (n)} in a reasonable time ? V. Brimkov and R. Barneva assumed that only exclusively down-right or up-right searches (with additional conditions) in Π(n, n ∞ ) are necessary to compute w 0 (see [START_REF] Brimkov | Connectivity of discrete planes[END_REF]). This assertion is false and here is a counter-example:

Example 1. Let n = (4, 7, 16). Let w 0 be the 0-connecting thickness of n. In Figure 3(a), both light paths are computed by V. Brimkov and R. Barneva's algorithm. Minimal remainders of each one are respectively 3 and 5, and the algorithm returns w 0 = max{3, 5} + 1 = 6. In Figure 3(b), one sees that Π(n, 6) is not 0-connected, and by Theorem 4, so is P(n, 6). In fact, the correct 0connecting thickness for the vector n is 7 as shown in Figure 3(c). This value is obtained with the dark grey path in Figure 3(a), which cannot be computed using exclusively up-right or down-right searches.

Arithmetic Reduction of an Arithmetic Discrete Plane

We have seen in Section 4, that V. Brimkov and R. Barneva's algorithm needs a graph traversal for computing the 0-connecting thickness of a given integer vector. Similarly, Y. Gérard proposed an algorithm, based on a graph traversal too, testing whether a given rational arithmetic discrete hyperplane is κ-connected. In the present section, we propose a reduction acting on the normal vector and the arithmetic thickness of an arithmetic discrete plane P(n, w) which returns an arithmetic discrete plane P(n ′ , w ′ ) with the same 0-connectedness as P(n, w) and such that |n ′ 1 | < |n 1 |. By iterating this reduction, we obtain in a finite time an arithmetic discrete plane P(n ′ , w ′ ) with a zero coordinate. The 0-connecting thickness (see Definition 2) of such a vector is easy to determine: Lemma 2. Let P(n, w) be a rational arithmetic discrete plane. Let us suppose there exists i ∈ {1, 2, 3} such that n i = 0. Then, P(n, w) is 0-connected if and only if w ≥ n ∞ . In other words, the 0-connecting thickness of n is n ∞ . Proof. It is well known that, if w ≥ n ∞ then P(n, w) is 0-connected [START_REF] Andres | Discrete analytical hyperplanes[END_REF].

Conversely, let us suppose, with no loss of generality, that n 1 = 0 and 0

≤ n 2 ≤ n 3 . Let x ∈ Z 2 such that n 1 x 1 + n 2 x 2 = n 2 x 2 ≡ n 3 -1 mod n 3 (remember we assume gcd{n 1 , n 2 , n 3 } = 1). Then, for all k ∈ Z, (x 1 + k)n 1 + x 2 n 2 = x 1 n 1 + x 2 n 2 ≡ n 3 -1 mod n 3 .
Hence, for all k ∈ Z, (x 1 + k, x 2 ) ∈ Π(n, w) and Π(n, w) is not 0-connected. The result follows from Theorem 4.

⊓ ⊔

Remember that, thanks to Theorem 4, one can reduce the determination of the 0-connectedness of the arithmetic discrete plane P(n, w) to the one of Π(n, w) = x ∈ Z 2 , n 1 x 1 + n 2 x 2 mod n 3 ∈ [0, w[ with n ∈ Z 3 and n 3 = n ∞ . Moreover, a direct consequence of Theorem 4 is: Lemma 3 (Symmetry Lemma [START_REF] Brimkov | Connectivity of discrete planes[END_REF]). Let Ω : N 3 → N be the function mapping each vector of N 3 to its 0-connecting thickness. For all

n ∈ Z 3 , if 0 ≤ n 1 , n 2 ≤ n 3 , then Ω(n 1 , n 2 , n 3 ) = Ω(n 3 -n 1 , n 2 , n 3 ) = Ω(n 1 , n 3 -n 2 , n 3 ) = Ω(n 3 -n 1 , n 3 - n 2 , n 3 ).
Given a vector n ∈ Z 3 , thanks to Lemma 3 and to the action of the isometry group of the cube on the set of arithmetic discrete planes, one suppose with no loss of generality and in order to compute the 0-connecting thickness of n that 0 ≤ 2n 1 ≤ 2n 2 ≤ n 3 .

Let us now state the main theorem of the present section: Theorem 6 (Arithmetic reduction). Let n ∈ Z 3 such that 0 ≤ 2n 1 ≤ 2n 2 ≤ n 3 and let w ∈ Z. Let (q, r) ∈ N 2 be the unique pair of integers such that

n 2 = qn 1 + r and r ∈ [0, n 1 [. Let n ′ = M • n with M =   1 0 0 -q 1 0 1 -q -1 1   ,
and let w ′ = w -(n 2n 1 ). Then, the arithmetic discrete plane P(n, w) is 0-connected if and only if so is the arithmetic discrete plane P(n ′ , w ′ ).

In order to prove Theorem 6, let us introduce in some sense the dual notion of the κ-connecting thickness of a vector:

Definition 3 (κ-separating thickness). Let n ∈ Z 3 and let κ ∈ {0, 1}. The κ-separating thickness w κ of n is the thickness of the thinnest κ-separating Π(n, w), with w ∈ Z.

An easy computation directly gives:

Lemma 4. Let n ∈ Z 3 such that 0 ≤ n 1 , n 2 ≤ n 3 and gcd{n 1 , n 2 , n 3 } = 1.
Let w 0 (resp. w 0 ) be the 0-connecting thickness (resp. 0-separating thickness) of n.

Then w 0 + w 0 = n 3 + 1. Proof. Let w ∈ N. Then Z \ Π(n, w) = (x 1 , x 2 ) ∈ Z 2 , n 1 x 1 + n 2 x 2 mod n 3 ∈ [w, n 3 [ = (x 1 , x 2 ) ∈ Z 2 , n 1 x 1 + n 2 x 2 -w mod n 3 ∈ [0, n 3 -w[ Let (α 1 , α 2 ) ∈ Z 2 such that n 1 α 1 + n 2 α 2 ≡ -w mod n 3 . Thus, Z \ Π(n, w) + (α 1 , α 2 ) = Π(n, n 3 -w)
and Π(n, w) is 0-connected if and only if Π(n, n 3w) is not 0-separating. Since Π(n, w 0 ) (resp. Π(n, w 0 -1)) is 0-connected (resp. is not 0-connected), then Π(n, n 3w 0 ) (resp. Π(n, n 3w 0 + 1)) is not 0-separating (resp. is 0-separating). Hence w 0 = n 3w 0 + 1 and the result follows.

⊓ ⊔

Since the κ-connectedness and the κ-separatingness of a rational arithmetic discrete plane do not depend on the translation parameter, an easy computation gives the equivalent reformulation of Theorem 6: Theorem 7 (Arithmetic reduction). Let n ∈ Z 3 such that 0 ≤ 2n 1 ≤ 2n 2 ≤ n 3 and let w ∈ Z. Let (q, r) ∈ N 2 be the unique pair of integers such that n 2 = qn 1 + r and r ∈ [0, n 1 [. Let n ′ = M • n with

M =   1 0 0 -q 1 0 1 -q -1 1   ,
and let w ′ = w-qn 1 . Then, Π(n, w) is 0-separating if and only if so is Π(n ′ , w ′ ). In the present paper, we presented an algorithm computing the 0-connecting thickness of any integer vector. The main difference between this algorithm and the ones already known [START_REF] Brimkov | Connectivity of discrete planes[END_REF][START_REF] Gérard | Periodic graphs and connectivity of the rational digital hyperplanes[END_REF] is that it does not need a graph traversal and only computes basic reductions on an integer vector.

Proof (sketch)

In a forthcoming work, we plan to investigate the case of non-rational arithmetic planes. Since the reduction of Theorem 6 does not depend on the nature of the input vector (integer or not), we hope to extend this approach to any vector n ∈ R 3 .

Other interesting investigations should be, on the one hand, the computation of κ-connected thickness for κ ∈ {1, 2} and, on the other, the extension of this work to arithmetic discrete hyperplanes in any dimension.

Fig. 1 .

 1 Fig. 1. From left to right: an arithmetic discrete line -a naive discrete plane -a standard discrete plane

2

 2 the arithmetic discrete hyperplane P(n, µ, w) is called an arithmetic discrete line and is denoted by D(n, µ, w). If d = 3 the arithmetic discrete hyperplane P(n, µ, w) is called an arithmetic discrete plane.

Definition 2 (

 2 κ-Connecting thickness). Let n ∈ Z d and κ ∈ {0, . . . , d -1}. The thickness w κ of the thinnest κ-connected arithmetic discrete hyperplane with normal vector n is called the κ-connecting thickness of n.

Fig. 2 .

 2 Fig. 2. Connected arithmetic discrete planes

Theorem 3 (

 3 [START_REF] Andres | Discrete analytical hyperplanes[END_REF]). Let P(n, w) be the arithmetic discrete hyperplane with normal vector n ∈ Z d and thickness w ∈ Z. Let κ ∈ {0, . . . , d -1}. The arithmetic discrete hyperplane P(n, w) is (d-κ-1)-separating in Z d if and only if w ≥ ]n[ κ .

Remark 2 .

 2 Let us remember that, thanks to Remark 1, the condition n ∞ = |v 3 | in Theorem 4 is not restrictive. Up to an isometry, one can similarly treat the cases n ∞ = |v 1 | and n ∞ = |v 2 |.

  Array of remainders Π(n, 6).(c) Array of remainders Π(n, 7).

Fig. 3 .

 3 Fig.3. Computation of V. Brimkov and R. Barneva's algorithm[START_REF] Brimkov | Connectivity of discrete planes[END_REF] on the vector n = (4, 7, 16)

Fig. 4 .

 4 Fig. 4. A 1-path corresponding to the triple (1, [-n2, n1, n1 -n3, -(n2 -n3), -n2, n1, n1, n1 -n3, n1], 4)

Acknowledgements

We would like to thank E. Andres for having pointed out the original problem to the authors. We also thank P. Arnoux, V. Berthe, V. Brimkov, C. Fiorio, Y. Gérard and D. Vergnaud for many interesting discussions on the subject.

the 1-path γ. ii) u ∈ {±n 1 , ±n 2 , ±(n 1n 3 ), ±(n 2n 3 )} k is a finite sequence of movements between A and B (see Figure 4) (the integer k ∈ N is called the length of u). Let us notice that the movements ±(n 1n 3 ) and ±(n 2n 3 ) corresponds to horizontal (resp. vertical) movements in Π(n, w) with a change of height in P(n, w). Such a change is represented by a thick line in the array of remainders (see Figure 4). Conversely, let (A, u, B) be a triple with (A, B)

The aim of this proof is to show that Π(n, w) admits an infinite 1-path if and only if so does Π(n ′ , w ′ ). Let us first prove that each pair of two 1-adjacent pixels in Π(n ′ , w ′ ) can be

The other cases, namely (A, n ′ 2 , B) and (A, n ′ 2n ′ 3 , B), are obtained in the same way. For summarize, see Figure 5 for a correspondance between a 1-path in Π(n ′ , w ′ ) and a 1-path in Π(n, w). Conversely, if Π(n, w) admits an infinite 1-

path, then by a similar recoding of it, one obtains an infinite 1-path in Π(n ′ , w ′ ). The complete proof if this theorem will appear in a forthcoming long version of the present paper.

⊓ ⊔

Algorithm

In the present section, we design an algorithm which computes the 0-connecting thickness of a given integer vector n ∈ Z 3 . It iterates the reduction introduced in Theorem 6 until 0-connecting thickness becomes easy to determine. The arithmetic reduction mentioned above only preserves 0-connectedness between the arithmetic discrete plane with normal vector n and its image under some conditions on n . Nevertheless changing the components of a vector according to the symmetry lemma 3 or sorting them do not change the associated 0-connecting thickness. It is then possible to find from any vector n a vector n ′ with the same 0-connecting thickness meeting the requirement of Theorem 6. A step consisting of application of symmetry lemma, sorting, and the arithmetic reduction can be repeated and turns the vector n into another vector n ′ such that n 1 ≤ n ′ 1 , n 2 < n ′ 2 and n 3 < n ′ 3 . Consequently, after a finite number of iteration, we always obtain a vector with a zero component for which the 0-connecting thickness is easy to determine. Algorithm 1 follows from those considerations. It always terminates since the stopping condition, that is a vector with a zero component, is always reached in a finite number of iteration.

Algorithm 1 Determination of the 0-connecting thickness.

Input : n ∈ N 3 . Output : w0 ∈ Z, the 0-connecting thickness of n.

ω ← 0 while n2 = 0 do {Symmetry and ordering} n1 ← min(n1, n3 -n1) n2 ← min(n2, n3 -n2) t ← min(n1, n2) n2 ← max(n1, n2) n1 ← t {Reduction} q ← ⌊n2/n1⌋ ω ← ω + (n2 -n1) n3 ← n3 -(n2 + (q -1)n1) n2 ← n2 -qn1 end while return ω + n3


Fine-grained Parallel ILU Preconditioners with Fill-ins for Multi-core CPUs and GPUs List of authors: D. Lukarski1 V. Heuveline2 J.-P. Weiss 3Numerical simulation and its huge computational demands require a close coupling between efficient mathematical methods and their hardware-aware implementation on emerging and highly parallel computing platforms. The paradigm shift towards manycore parallelism not only offers a high potential of computing capabilities but also comes up with urgent challenges in designing scalable, portable, and flexible software solutions. The latter point is closely related to adaptation, variation, and restructuring of algorithms and numerical schemes in order to be compliant with coarse-and fine-grained parallelism, hierarchical memory subsystems, heterogeneous platforms, and any kind of communication bottleneck. Numerical codes should not only be efficient and robust, but also future-proof with respect to the current dynamic landscape of hardware platforms and parallel programming environments. The goal of our work is to treat problems with great impact on science and humanities, e.g. in the domain of meteorology, medical engineering and energy research, can be modeled and solved. With efficient preconditioners the bounds of solvability can be pushed further beyond.

Complex problem domains and the need for high accuracy typically result in huge systems that are sparse, closely coupled, and with bad condition numbers. A classical choice for iterative solvers are Krylov subspace methods like conjugate gradient (CG) for symmetric and positive definite systems and the generalized minimal residual (GMRES) method. In both cases, the number of iterations depends on the condition number and grows polynomially in the problem size. Good preconditioners should fullfil several properties. First, they should mitigate the costs in terms of necessary iterations by restructuring the problem matrix and affecting its spectrum and condition number. Second, since in each iteration step an additional linear system has to be solved, the additional effort should not outweigh achieved benefits. Third -and this point is becoming much more important due to the development towards manycore computing platforms -the preconditioner has to comprise a high degree of parallelism. Fourth, the preconditioner should be applicable to a large class of problems where only minimal additional information is available on specific matrix properties. The latter point is particularly important for the inclusion of preconditioners into widely applicable solver suites. As experience shows, parallelism for preconditioners based on reduced couplings comes at the expense of reduced preconditioning efficiency. So preconditioning also means to find a trade-off between several aspects. The HiFlow 3 finite element software tackles productivity and performance issues by its con-ceptual approach [START_REF] Anzt | HiFlow 3 -A Flexible and Hardware-Aware Parallel Finite Element Package EMCL[END_REF]. Efficient numerical solvers are built on the basis of unified interfaces to different hardware platforms and parallel programming approaches in order to obtain modular and portable software solutions on emerging systems with heterogeneous configuration. With the concept of object-orientation in C++, the HiFlow 3 finite element software provides a flexible, generic, and modular framework for building efficient parallel solvers and preconditioners for partial differential equations of various types. It comprises a complete set of BLAS 1 and 2 linear algebra routines and data access routines for all platforms. For scalable and portable parallelism all solvers are built upon a two-level library. The linear algebra toolbox (LAtoolbox) orchestrates computations and communications across nodes by an MPI layer. Underneath, the local multi-platform linear algebra toolbox (lmpLAtoolbox) provides highly efficient and optimized implementations with backends to various platforms (e.g. CUDA, OpenMP, OpenCL) where parallelism is expressed by means of data parallelism. Further platforms can be added easily. The user can build modular solutions by utilizing unified interfaces on an abstract level. The same source code for the solver and the preconditioners can be used on several platforms including GPUs. The final choice of platform and particular implementation is taken at run-time. This approach enables user-friendly and scalable solutions in heterogeneous environments.

In this work we describe our efforts for building efficient preconditioning schemes for Krylov subspace iterative solvers in the context of the HiFlow 3 parallel finite element solver package [START_REF]HiFlow 3 -Parallel Finite Element Package[END_REF]. Our main intention is to construct preconditioners with a high degree of parallelism. Structure and organisation of the HiFlow 3 software into several modules and communication layers with unified interfaces for the programmer allows to write a single code base that can be run across a wide range of parallel platforms including multi-core CPUs, graphics processing units (GPUs), and OpenCL-capable accelerators. Since GPU code should be scalable to thousands of threads, our approach is to identify parallelism on the level of blocks within block-decompositions and not only on the level of non-scalable parallel execution of blocks.

We consider preconditioners in block form based on additive matrix splittings like e.g. Gauß-Seidel and SOR, and multiplicative decompositions like incomplete LU (ILU). All our considered preconditioners are based on the block-wise decomposition into small sub-matrices. In both scenarios, typically a large amount of forward and backward sweeps in triangular solvers need to be performed. In order to harness parallelism within each block of the decomposition we use matrix reordering techniques like multi-coloring. For splitting-based methods (Gauß-Seidel, SOR) and ILU(0) without fill-ins the original matrix pattern is preserved. But before solving the preconditioned system, the matrix is reorganized such that diagonal blocks are diagonal itself. Then, inversion of the diagonal blocks is just an easy vector operation [START_REF] Heuveline | Scalable Multi-Coloring Preconditioning for Multi-core CPUs and GPUs UCHPC'10[END_REF]. In the multicoloring approach sets of independent nodes -called colors -are identified. The number of colors depends on the mesh, the choice of finite element spaces, and on the problem dimension. A performance analysis for a convection-diffusion problem solved by Q1 and Q2 elements in two and three dimensions is presented in [START_REF] Heuveline | Parallel Preconditioning and Modular Finite Element Solvers on Hybrid CPU-GPU Systems submitted[END_REF]. The scalability and efficiency of our approach has been proven in [START_REF] Heuveline | Scalable Multi-Coloring Preconditioning for Multi-core CPUs and GPUs UCHPC'10[END_REF][START_REF] Heuveline | A Multi-Platform Linear Algebra Toolbox for Finite Element Solvers on Heterogeneous Clusters PPAAC'10[END_REF]. Furthermore, we allow fill-ins in the ILU(p) method for achieving higher level of coupling with increased efficiency. Here, we consider two algorithms for parallelism: level-scheduling method [START_REF] Saad | Iterative Methods for Sparse Linear Systems Society for Industrial and Applied Mathematics[END_REF] and our adding auxiliary colors algorithm. In our experiments, we apply both techniques to matrices with a symmetric pattern of non-zero elements. The first method is used as a postprocessing method following the factorization where the level of parallelism for the elimination processes in the forward and backward sweeps is determined and utilized. However, this method produces very small blocks for many problem classes, i.e. the degree of parallelism is low. An improvement with respect to the level of parallelism can by obtained by applying multi-coloring to the original matrix in first place. As a second approach we have developed our new technique that adds further colors to the original matrix resulting in diagonal matrices on the diagonal blocks combined with ILU(p) with additional fill-in. This approach provides a much higher degree of parallelism compared to the level-scheduling method.

We present a detailed performance analysis on several multi-core platforms and GPU configurations -proofing viability and benefit of our solution. In combination with HiFlow 3 's cross-platform portable concept, we provide flexible and scalable iterative solvers combined with efficient parallel preconditioners based on splitting methods and parallel ILU(p).

SRG New Frontiers in High Performance Computing, Engineering Mathematics and Computing Lab (EMCL), Karlsruhe Institute of Technology (KIT), Germany

Engineering Mathematics and Computing Lab (EMCL), Karlsruhe Institute of Technology (KIT), Germany

SRG New Frontiers in High Performance Computing, Engineering Mathematics and Computing Lab (EMCL), Karlsruhe Institute of Technology (KIT), Germany