Portfolio à destination des guides de Pétra

(Syrie du Sud) (Fig. 4), nous incite restituer de manière hypothétique de larges baies thermales vitrées (verre sur armature bois ou maçonnerie légère).

Une dernière campagne de fouille prévue en octobre 2017 sur l'édifice devrait permettre de lever certaines des hypothèses exposées dans cette restitution provisoire. Elle permettra également d'achever les travaux de conservation engagées lors de la précédente campagne (en particulier sur la façade ouest, traitée en parapet eu niveau de la falaise, destiné à sécuriser la visite de l'édifice).

Les résultats de l'étude des bains devraient faire l'objet d'une présentation au Troisième colloque international sur Pétra et la culture nabatéenne (Strasbourg, 18-21 juin 2018).

Bibliographie

  Fig. 1 : vue d'ensemble des bains du Jabal Khubthah depuis le nord-est (N. Paridaens, 2016) Fig. 2 : proposition de restitution des bains du Jabal Khubthah à l'époque romaine, depuis le sud-est (Th. Fournet, 2017)

TABLE DES MATIERES

 DES

	1. Introduction	7
	1.1. Le quadriennal 2016-2019 : appuis à la recherche	7
	1.2. Les campagnes d'octobre 2016 et de mai 2017	10
	1.3. Remerciements	10
	1.4. Les équipes de recherche	11
	1.5. Financements et partenariats	12
	1.6. Publications 2016/2017	12
	1.7. Communication	15
	1.8. Conservation, restauration et mise en valeur	16
	1.9. Formation	17
	1.10. Résumé du programme 2016/2017	17
	2. Rapports individuels par secteur / site	19
	2.1. Pétra -Qasr al-Bint. La campagne d'octobre 2016	19
	François Renel
	2.2. Pétra -Qasr al-Bint. Une première étude architecturale du « Bâtiment B »	43
	Thibaud Fournet
	2.3. Pétra -Les bains du Jabal Khubthah : étude architecturale (2016 -2017)	63
	Thibaud Fournet & Nicolas Paridaens
	3. Restauration	69
	3.1. La restauration du monument à exèdre : la façade orientale (octobre 2016)	69
	Jean Brunet
	3.2. Le projet de conservation, restauration et présentation du Qasr al-Bint :
	la campagne de conservation des escaliers du Qasr (mai 2017)	79
	Soizik Bechetoille-Kaczorowski
	4. Études matérielles	87
	4.1. L'occupation tardive du triclinium BD 290 (« Chapelle d'Obodas »,
	Jabal Numayr, Pétra) Étude du matériel céramique	87
	Caroline Durand
	4.2. Les monnaies des fouilles de la Mission archéologique française à Pétra :
	rapport de la mission d'étude de mai 2017	97
	Christian Lauwers

  Broise 1991 H. Broise, « Vitrages et volets des fenêtres thermales à l'époque impériale », dans Les thermes romains. Actes de la table ronde de Rome(11-12 novembre 1988), (Collection de l'École française de Rome 142), p. 61-78.

4 Il est connu, tant par les textes que par l'archéologie, que les bains possédaient de larges fenêtres vitrées, par lesquelles la vue était possible : Broise 1991 ; Vipard 2009. 5 Fournet 2010.

Ce dessin servira dès octobre à une signalétique sur le terrain, à Pétra même, et sera utilisé courant

dans une numéro thématique « Pétra » des Dossiers de l'Archéologie. 2 Voir le rapport 2016, p. 92-93. 3 Voir le rapport 2016, fig. 7, p. 84.

Fournet 2010 Th. Fournet, « Les bains romains de Sleim (Selaema), analyse architecturale et proposition de chronologie », dans Hauran V. La Syrie du Sud du Néolthique à l'Antiquité Tardive, recherches récentes, vol. 1, dir. M. al-Maqdissi, F. Braemer, J.-M. Dentzer, BAH 191, p. 315-334. Vipard 2009 P. Vipard, « L'usage du verre à vitre dans l'architecture romaine du Haut Empire, in S. Lagabrielle, M. Philippe (Éds), Verre et fenêtre de l'Antiquité au XVIIIe siècle. Actes du premier colloque international de l'association Verre et Histoire, Paris-La Défense / Versailles, 13-15 octobre 2005, Paris, 2009, p. 3-10.

Couverture de l'édifice

Certains espaces ne posaient pas de réels problèmes de restitution (c'est le cas par exemple de la citerne / château d'eau 8, dont l'encastrement des arcs de couverture est conservé dans la roche), et peuvent être considérés comme certains. Le mode de couverture du reste de l'édifice est moins évident. La portée maximale des salles thermales (entre 2,90 m et 3,20 m) permet d'imaginer plusieurs modes de couverture : arcs parallèles portant dalles, poutraison bois et solivage, voûtes.

L'absence de blocs en position de chute, qui s'explique par la situation très exposée de l'édifice et sa réoccupation tardive, ne permet aucune certitude. Il est cependant probable qu'à l'image d'édifices thermaux mieux conservés une couverture voûtée ait été choisie. Elle répond mieux qu'une charpente aux contraintes subies par un édifice constamment soumis à la chaleur et à l'humidité. La faible épaisseur des maçonneries (en particulier le mur est-ouest séparant les salles 2 et 4, épais de seulement 50 cm) n'est pas incompatible avec cette solution, les voûtes proposées, attestées ailleurs à Pétra, étant elles même peu épaisses (env. 30 cm), et leurs poussées étant reprises, au nord et au sud, par des massifs plus stables (le rocher au sud, le bloc du caldarium au nord). Ce choix de voûtes en plein cintre s'appuie également sur la découverte, dans la fouille du caldarium, de plusieurs blocs clavés.

La salle de service 6 (salle de chauffe, au nord de l'édifice) est en grande partie aménagée dans le rocher. La présence d'une porte dans son angle nord-est semble indiquer que là où le rocher disparait, une maçonnerie venait fermer la pièce. Nous n'avons en revanche aucun indice d'une éventuelle couverture de la pièce, qui pouvait parfaitement être en partie hypèthre, en particulier pour faciliter l'évacuation des fumées non évacuée par l'hypocauste.

Dispositifs de chauffage

Par soucis de lisibilité, pour éviter de surcharger le dessin, les parois creuses de tubulure n'ont pas été représentées. Il a en revanche été choisi « d'ouvrir » le sol du caldarium 5, afin de révéler le dispositif d'hypocauste révélé par la fouille. Seul le foyer nord du caldarium est visible sur le dessin, et correspond foyer principal de l'édifice. Le faible niveau de conservation de ce secteur des bains ne permet pas de restituer avec certitude les dispositifs associés à ce foyer. Il est cependant possible, au regard du niveau d'ouverture conservé du praefurnium, qu'un dispositif de chauffage direct de l'eau du bassin ait existé, juste au-dessus du foyer (système de testudo alvei, chaudière métallique connectée au bassin maçonné), comme cela devait souvent être le cas dans les bains de cette époque.

C'est en tout cas ce que nous avons décidé de représenter. La présence d'une véritable chaudière en avant du foyer en revanche n'a été qu'esquissé en pointillés légers, ce dispositif n'ayant laissé aucun vestiges bâtis. Nous sommes cependant tentés de le restituer, les bains pouvant difficilement fonctionner sans chaudière, et cette dernière n'ayant la place d'exister qu'au niveau de ce foyer (les autres praefurnia, accessibles depuis un étroit couloir de service à l'ouest (7), ne disposent pas du recul suffisant). La présence, en avant du foyer, d'une dépression ovoïde très marquée par le feu serait la seule trace de cet aménagement.


S A Shahzadeh Fazeli
email: fazeli@yazduni.ac.ir

N Emad

Z Liu

A KEY TO CHOOSE SUBSPACE SIZE IN IMPLICITLY RESTARTED ARNOLDI METHOD

Keywords: Large eigenproblems, Krylov subspace size, Arnoldi method, implicit restarting AMS subject classifications. 65F15, 15A18

The implicitly restarted Arnoldi method (IRAM) computes some eigenpairs of large sparse non Hermitian matrices. However, the size of the subspace in this method is chosen empirically. A poor choice of this size could lead to the non-convergence of the method. In this paper we propose a technique to improve the choice of the size of subspace. This approach, called multiple implicitly restarted Arnoldi method with nested subspaces (MIRAMns) is based on the projection of the problem on several nested subspaces instead of a single one. Thus, it takes advantage of several different sized subspaces. MIRAMns updates the restarting vector of an IRAM by taking the eigeninformation of interest obtained in all subspaces into account. With almost the same complexity as IRAM, according to our experiments, MIRAMns improves the convergence of IRAM.

1. Introduction. In the fluid dynamics, economic modelling and some other domains there are a number of cases where a few eigenvalues with the largest real part or with the largest magnitude of a nonsymmetric matrix are required. Several methods have been proposed to solve this kind of eigenproblems. Arnoldi in 1951 [START_REF] Arnoldi | The Principle of Minimized Iteration in the Solution of Matrix Eigenvalue Problems[END_REF] proposed a method which is a variant of the Krylov projection methods. The Arnoldi method is an efficient technique which permits to compute an approximation of desired eigenpairs of an n-size matrix A by those of an m×m matrix representing A in an m-size Krylov subspace (with m ≤ n). Meanwhile, when the wanted eigenvalues are clustered the Krylov subspace ought to have overly large size. The Arnoldi method is best at finding a solution to an eigenproblem with well-separated eigenvalues. A drawback of this method is the expense of too much memory space when m is large. This problem is solved by restarting the method as proposed in 1980 by Saad [START_REF] Saad | Variations on Arnoldi's Method for Computing Eigenelements of Large Unsymmetric Matrices[END_REF].

Saad's approach, called explicitly restarted Arnoldi method (ERAM), restarts the Arnoldi projection with a better subspace. Indeed, this approach offers to choose a small Krylov subspace (m ≪ n). Then, if the accuracy of the desired Ritz elements computed by Arnoldi method is not satisfactory, ERAM restarts the process using a new Krylov subspace. This new subspace differs by the last one by its initial vector which is formed by an explicit combination of the computed Ritz elements. Although this algorithm is attractive for reason of simplicity, the formation of a restarting vector for the next restart cycle using the approximated eigenvectors of the current cycle might not be good. The restarting is difficult because one new starting vector must be defined as an explicit linear combination of wanted Ritz vectors. If this combination is not carefully chosen, it can lead to a very bad selection for the new starting vector. Moreover, when the starting vectors are complex the cost will increase. Saad proposed some special coefficients for the combination of Ritz vectors such as the weighted linear combination [START_REF] Saad | Variations on Arnoldi's Method for Computing Eigenelements of Large Unsymmetric Matrices[END_REF]. As himself mentioned it, this method may not well work in practice for many eigenproblems [START_REF] Saad | Numerical Solution of Large Nonsymetric Eigen Problem[END_REF]. Moreover, the problem of the choice of the size of the subspace remains. An approach based on the Arnoldi projection onto several Krylov subspaces is proposed by Emad et al [START_REF] Emad | Multiple Explicitly Restarted Arnoldi Method for Solving Large Eigenproblems[END_REF]. The latter are formed with different initial vectors and have different sizes. This technique is called multiple explicitly restarted Arnoldi method (MERAM). It updates the restarting vector of each ERAM process by taking into account the eigen-information of interest obtained by all ERAM processes. MERAM improves often the convergence of ERAM but the restarting issues intrinsic to ERAM remain [START_REF] Emad | Multiple Explicitly Restarted Arnoldi Method for Solving Large Eigenproblems[END_REF].

In order to improve the Arnoldi method, Sorensen has suggested an efficient technique which makes use of the QR algorithm to restart the Arnoldi projection [START_REF] Sorensen | Implicit Application of Polynomial Filters in a k-step Arnoldi Method[END_REF]. His approach permits to restart the Arnoldi process with an efficient and numerically stable formulation. This approach which is called implicitly restarting Arnoldi method (IRAM) was analyzed, implemented and validated, among others, in [START_REF] Sorensen | Implicit Application of Polynomial Filters in a k-step Arnoldi Method[END_REF][START_REF]Lehoucq Analysis and Implementation of an Implicitly Restarted Iteration[END_REF][START_REF] Lehoucq | Deflation techniques for an implicitly restarted Arnoldi iteration[END_REF][START_REF] Sorensen | Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations[END_REF][START_REF] Lehoucq | ARPACK User's Guide: Solution of Large Scale Eigenvalue Problems With Implicitly Restarted Arnoldi Methods[END_REF][START_REF] Maschhoff | An efficient portable large scale eigenvalue package for distributed memory parallel architectures[END_REF]. As in ERAM, implicity restarted Arnoldi method makes use of Arnoldi projection to approximate the desired eigenpairs of a large matrix A. If the accuracy of these Ritz elements is not satisfactory, IRAM applies a QR shifted algorithm on the m × m matrix which represents A in the projection subspace. As these are the non desired eigenvalues which are chosen for shifts, the upper-left block of the matrix issued from QR algorithm concentrates the information corresponding to the desired eigenvalues. IRAM completes an m-size Arnoldi projection starting with the submatrix representing this block whose size is the number of wanted eigenvalues. This is equivalent to restart the Arnoldi process with a new initial vector computed implicitly. Morgan showed that IRAM is much better than the other restarting Arnoldi methods such as explicitly restarted ones [START_REF] Morgan | On Restarting the Arnoldi Method for Large Nonsymmetric Eigenvalue Problem[END_REF]. However, the problem of choosing the size of subspace remains.

In restarted Arnoldi methods, in order to improve the quality of the subspace during the restart cycles, only the initial vector is taken into account. We propose to make this improvement by taking into account both the initial vector and the size of the subspace. For this, we propose to apply the same idea as the one used in MERAM. This approach called multiple implicitly restarted Arnoldi method with nested subspaces (MIRAMns), is based upon the projection of the problem on several Krylov subspaces instead of a single one. These subspaces differ by their size while the subspaces in multiple restarted methods such as MERAM can differ by their size and their initial vectors [START_REF] Emad | Multiple Explicitly Restarted Arnoldi Method for Solving Large Eigenproblems[END_REF]. MIRAMns makes use of Arnoldi method to compute the Ritz elements of a large matrix A in a set of ℓ nested Krylov subspaces K mi,v (for i = 1, . . . , ℓ) with K mi,v ⊂ K mi+1,v . If the accuracy of the desired Ritz elements calculated in these subspaces is not satisfactory, MIRAMns selects the "best" of these subspaces. This subspace is one that contains the "best" current Ritz elements. Then a QR shifted algorithm will be applied to the m best × m best matrix which represents A in this m best -size projection subspace. As these are the non desired eigenvalues which are chosen for shifts, the leading submatrix issued from QR algorithm concentrates the information corresponding to the desired eigenvalues. MIRAMns completes Arnoldi projections on ℓ nested Krylov subspaces starting with this submatrix whose size is the number of wanted eigenvalues.

One of the well known problems of the restarted iterative methods is the sensitivity of the convergence with respect to small perturbations of the subspace size. Indeed, they could not converge with a subspace and converge with the same reduced/extended subspace with nearby sizes. MIRAMns overcomes to this problem by making choice of the "best" size among these subspace sizes. Another advantage of this technique is the better property of convergence with almost the same time complexity relative to IRAM. Our experiments showed a very good acceleration of convergence with respect to the implicitly restarted Arnoldi method.

This paper has the following organization. An overview of the related work is presented in the next section. The implicitly restating Arnoldi method is discussed in section 3. The multiple implicitly restarted Arnoldi method with nested subspaces and an algorithm of it are presented in section 4. Section 5 is devoted to numerical experiments. Finally we present a conclusion in the last section.

Definition and notation. Let A be a complex non-Hermitian matrix of dimension n × n, v be an n-size initial guess, K m,v1 be the Krylov subspace spanned by

(v 1 , Av 1 , . . . , A m-1 v 1 ) with v 1 = v/ v 2 and (v 1 , • • • , v m )
AV m = V m H m + f m e T
m is called an m-step Arnoldi factorization, where H m ∈ C m×m is an upper Hessenberg matrix with non-negative subdiagonal elements,

V m ∈ C n×m is a matrix with orthonormal columns v 1 , • • • , v m and V H m f m =
0 where f m is the residual vector of lenght n. This factorization can be used to reduce the eigenproblem with the large order matrix A to a problem with a smaller order matrix H m . Let y (m) i be an eigenvector of H m associated with the eigenvalue λ (m) i and u

(m) i = V m y (m) i . (u (m) i , λ (m) i
) is an approximate eigenpair for A called also Ritz eigenpair and 2. Related work. The paper [START_REF] Lehoucq | Implicitly Restarted Arnoldi Methods and Subspace Iteration[END_REF] explains the relationship between the subspace size in IRAM and its convergence rate so the relevance of the subspace size has been discussed in the open literature. Dynamic selection of restart parameters in Arnoldi methods have been considered previously. Duff and Scott in [START_REF] Duff | Computing selected eigenvalues of large sparse unsymmetric matrices using subspace iteration[END_REF] developed a subspace algorithm combined with Chebychev acceleration. They select dynamically the size of the subspace and the degree of the Chebychev polynomial at each restart cycle. Stathopoulos, Saad and Wu proposed in [START_REF] Stathopoulos | Dynamic Thick Restarting of the Davidson, and the Implicitly Restarted Arnoldi Methods[END_REF] a technique, called thick restarting, than restarts the Arnoldi algorithm with more eigenvectors that is actually required. A dynamic thick restarting scheme which adjusts the number of retained Ritz vectors at each cycle in IRAM is proposed and the question of which and how many eigenvectors to retain is addressed for symmetrical eigenproblems. Some authors suggested more similar approaches to the one proposed in this paper. Baker et al. proposed in [START_REF] Baker | A Simple Strategy for Varying the Restart Parameter in GMRES(M)[END_REF] a simple strategy and provide some heuristic explanation for its effectiveness. The authors define a range of subspace sizes whose minimum and maximum values are respectivily m min and m max and they choose, according to some criterion the subspace size m i of the ith restart cycle in this discrete interval. Their strategy checks the convergence rate r i+1 2 / r i 2 at the end of each restart cycle, where r i is the residual vector of ith cycle. The subspace size is initialized by m max . When stagnation is detected, they decrease the restart parameter by a small number d at each cycle until reaching m min . At that point, they increase m i up to the maximum value m max . For the solution of non-symmetric linear systems by deflated GMRES, Moriya and Nodera proposed in [START_REF] Moriya | The DEFLATED-GMRES(m, k) method with switching the restart frequency dynamically[END_REF] a similar dynamic switching approach for the Krylov subspace dimension. Their strategy consists to combine the deflated GMRES algorithm and the determination of a restart parameter m dynamically. Indeed, in order to decrease the computation cost, the authors propose to begin with a small restart parameter m s . If stagnation in encountered then the restart parameter is switched to a larger value m l . When the restart value is m l and the stagnation disappears then the restart parameter is switched again to m s . They use as a criterion for stagnation the angle between the residual vector and search vectors which could be easily computed during a run of GMRES. Dookhitram et al. proposed in [START_REF] Dookhitram | A new method for accelerating Arnoldi algorithms for large scale Eigenproblems[END_REF] a comparable approach to accelerate the convergence of IRAM which is based on a relationship between the residual of the current restart cycle of IRAM and the residual in the previous cycle. Despite the similarity, their technique differs from that proposed by Moriya and Nodera for linear systems since unlike the latter, they do not initialize any angle to avoid a problem dependent strategy and also their switching strategy is based on a different relationship between the residual of the current restart cycle and the residual of the previous cycle.

ρ i,m = (A -λ (m) i I)u (m) i 2 = (AV m -V m H m )y (m) i 2 = |β m e T m y (
In the approach proposed in this paper, the dynamic determination of subspace size parameter is monitored and used inside the current restart cycle while in the methods cited above, this determination is done in current restart cycle for being used in the next restart cycle. In other words, the dynamicity of our approach is intra-cycle, while in the approaches mentioned above, the dynamicity is inter-cycle. Some results of the comparison with the methods proposed in [START_REF] Stathopoulos | Dynamic Thick Restarting of the Davidson, and the Implicitly Restarted Arnoldi Methods[END_REF] and [START_REF] Dookhitram | A new method for accelerating Arnoldi algorithms for large scale Eigenproblems[END_REF] are shown in the section 5.

3. The Sorensen approach. This variant of the Arnoldi method based on restarting technique is called implicitly restarted Arnoldi method (IRAM). That is a technique that combines the implicitly shifted QR mechanism with an Arnoldi factorization and can be viewed as a truncated form of the implicitly shifted QRiteration [START_REF] Sorensen | Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations[END_REF]. This method involves an implicit application of a polynomial in A to the starting vector. IRAM computes a few eigenvalues (k ≤ m) such as those of the largest real part or the largest magnitude. An m-step Arnoldi factorization

AV m = V m H m + f m e T m , (3.1)
is compressed to a factorization of length k with the eigen-information of interest. This is achieved using QR steps to apply p = m -k shifts implicitly. The results after the shift process and equating the first k columns on both sides are

AV + m = V + m H + m + f m e T m Q, (3.2) where V + m = V m Q, H + m = Q T H m Q, and Q = Q 1 Q 2 • • • Q p with Q j the orthogonal matrix in QR process associated with the shift µ (m) j and AV + k = V + k H + k + f + k e T k , (3.3) with f + k = V + m e k+1 β k + f m σ k where β k = H + m (k + 1, k) and σ k = Q(m, k).
Using this as a starting point one can apply p additional steps of the Arnoldi process to obtain an m-step Arnoldi factorization. Each shift cycle involves the implicit application of a polynomial in A of degree p to the starting vector v:

ψ(A)v with ψ(λ) = Π p j=1 (λ - µ (m) j
). The roots of this polynomial are the shifts used in the QR algorithm [START_REF] Sorensen | Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations[END_REF]. The resulting algorithm takes the form of the algorithm 1.

The stopping criterion in above algorithm can be computed by the expression called Ritz estimate:

(a)-|β m e T m y (m) i
|, or by its mathematically equivalent explicit

Algorithm 1 Implicitly restarted Arnoldi method Input: (A, V m , H m , f m ) with AV m = V m H m + f m e T m an m-step Arnoldi factorization For it = 1, . . ., until convergence 1.
• Compute σ(H m ) the eigenvalue of H m and their associated eigenvectors,

• Compute residual norm, if convergence stop, 2. Select set of p = m -k shifts (µ (m) 1 , • • • , µ (m)
p ), based upon σ(H m ) or other information and set q T ← e T m , 3. For j = 1, 2, . . . , p

• Factor [Q j , R j ] = qr(H m -µ (m) j I); • H m ← Q H j H m Q j ; V m ← V m Q j ; • q H ← q H Q j ; 4. Set f k ← v k+1 β k + f m σ k , V k ← V m (1 : n, 1 : k), H k ← H m (1 : k, 1 : k) 5. Beginning with the k-step Arnoldi factorization AV k = V k H k + f k e T k , Apply p additional steps of the Arnoldi process to obtain a new m-step Arnoldi factorization AV m = V m H m + f m e T m formula of the residual norm: (b)-(Au (m) i -λ (m) i u (m) i ) 2 (for i = 1, • • • , k).
Criterion (a) has a computational cost much lower than that of (b). However, criterion (b) may better represent the residual corresponding to the Ritz elements and is more reliable when rounding errors are present. This is because the expression of (b) contains computed Ritz elements and thus takes into account the rounding errors in their calculation. It should be noted that, as explained in [START_REF] Sorensen | Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations[END_REF][START_REF] Parlett | The Symmetric Eigenvalue Problem[END_REF], when A is Hermitian, the relation ((a)=(b)) may be used to provide computable rigorous bounds on the accuracy of the eigenvalues of H m as approximations to eigenvalues of A. When A is non-Hermitian the possibility of non-normality precludes such bounds and one can only say that the residual norm (Au

(m) i -λ (m) i u (m) i ) 2 is small if |β m e T m y (m) i
| is small. Note that if v = n j=1 γ j u j , the implicit restarting Arnoldi method with exact shifts provides a specific selection of expansion coefficients γ j for a new starting vector as a linear combination of the current Ritz vectors for desired eigenvectors. Implicit restarting provides a way to extract eigen-information of interest from large Krylov subspaces while avoiding the storage and numerical difficulties. This is done by continually compressing eigen-information of interest into an k-dimensional subspace of fixed size. This means that IRAM continues an m-step Arnoldi factorization, having kept all Ritz vectors of interest.

Time and space complexities of IRAM. We assume that m ≪ n. Therefore, in the time complexity expression of IRAM we can disregard terms not containing n. Let nrc be the number of restart cycles excluding the input step in the above algorithm. The cost of IRAM in terms of matrix-vector products for nrc restart cycles with (a) criterion is [m + (it -1) × (m -k)]. Indeed, in the first restart cycle the number of matrix-vector products is m and for each of the other restart cycles, the number of matrix-vector products is p = (m -k). The cost of IRAM will be increased by it × k, if (b) criterion is used. Noted that the cost of orthogonalization in a restart cycle is O() = m 2 n + O(n)?. When A is sparse and p is large, this cost of orthogonalization may dominant the computation.

The space complexity of IRAM is O(n 2 + m × n).

Multiple IRAM with nested subspaces (MIRAMns).

The purpose of restarting m-step Arnoldi factorization is to improve the quality of the initial Krylov subspace K m,v . This objective can be achieved by improvement of the vector v and/or the subspace size m. Indeed, the information obtained through the m-step Arnoldi factorization process is completely determined by the choice of the starting vector v and the subspace size m. The current Arnoldi (explicit/implicit) restarting techniques propose an amelioration of the initial vector v. Regarding the size of the subspace, it is known that the eigen-information of interest may not appear when m is too small [START_REF] Sorensen | Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations[END_REF]. Furthermore, if m is too large, the computation cost of orthogonalization process becomes excessive. The size of the subspace has to be chosen as a compromise between these factors and is chosen empirically according to the number of desired eigen-elements, the size of the original problem, etc. Here, we present a way to increase the quality of the Krylov subspace by improving the size of the subspace. Indeed, to remedy the essential question of the choice of the size of the subspace, this paper suggests the proliferation of these subspace sizes and to select the best one. The size of the subspace is chosen dynamically in every restarting step.

This approach consists to make use of IRAM with a set of Krylov subspaces which differ only by their size which means a set of nested subspaces. Let v be an initial vector and

M = (m 1 , • • • , m ℓ ) be a set of ℓ subspace-sizes with m 1 < • • • < m ℓ .
We built ℓ Arnoldi projections on the subspaces K mi,v (for i = 1, . . . , ℓ) where

K m1,v ⊂ K m2,v ⊂ . . . ⊂ K m ℓ ,v .
We select then the subspace size m best corresponding to the Arnoldi factorization which offers the Ritz estimates for k desired eigenpairs. The steps 2 to 4 of IRAM algorithm (i.e. algorithm 1) are applied then onto this Arnoldi factorization:

AV m best = V m best H m best + f m best e T m best .
That means only this factorization among the ℓ ones will be compressed to a factorization of length k with the eigen-information of interest. This is achieved using QR steps to apply p best = m best -k shifts implicitly. The results after the shift process and equating the first k columns on both sides are the same as in equation (3.3) with m = m best . Beginning with this resulting k-step Arnoldi factorization, we apply then p i = m i -k additional steps of Arnoldi factorizations to obtain ℓ new projections onto the updated subspaces (for i = 1, • • • , ℓ). This allows again the projection onto ℓ nested subspaces with initial guess determined by the compressed k-step Arnoldi factorization issued from the QR shifted applied to m best -step Arnoldi factorization.

We notice that this technique updates the restarting vector v by taking the eigeninformation obtained by several subspaces into account. Moreover, for a given restart cycle MIRAMns has almost the same time complexity as IRAM with the largest subspace size. Besides, in MIRAMns as in IRAM, the appearance of spurious eigenvalues may be avoided through complete reorthogonalization of the Arnoldi vectors using the DGKS correction [START_REF] Sorensen | Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations[END_REF][START_REF] Daniel | Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization[END_REF]. An algorithm of this method to compute k (k ≤ m 1 ) desired Ritz elements of A is presented by the algorithm 2.

In order to select the best results in the step (2) of the algorithm 2 we suppose that (

V mi , H mi , f mi ) is "better" than (V mj , H mj , f mj ) if r mi k < r mj k
where r mi k = max(ρ 1,mi , . . . , ρ k,mi ) is defined by Ritz estimates when (a) stopping criterion is used. The r mi k value is defined by the residual norm of Rayleigh quotient corresponding to (V mi , H mi , f mi ) when (b) stopping criterion is used.

Time and space complexities of MIRAMns.

As for IRAM, we can disregard the terms not containing n. Recall that m ℓ is the maximum of m 1 , . . . , m ℓ subspace sizes. The cost of MIRAMns in term of matrix-vector products with (a) criterion is [m ℓ + (nrc -1) × (m ℓ -k)] where nrc is the number of restart cycles. This cost will be increased by (ℓ

× k × nrc) if (b) criterion is used. Still the cost of orthogonalization in Arnoldi process is about m 2 l n + O(n).
As a result, this cost Algorithm 2 Multiple IRAM with nested subspaces Input: (A, V mi , H mi , f mi ) with AV mi = V mi H mi + f mi e T mi the m i -steps Arnoldi factorization (i = 1, 2, . . . , ℓ) For it = 1, 2, . . . until convergence 1.

• Compute σ(H mi ) and their associated eigenvectors (for i = 1, . . . , ℓ)

• Compute residual norms. If convergence in one of subspaces then stop. 2. Select the best results in these subspaces and the associated best subspace size

m best . Set m = m best , H m = H m best and V m = V m best , f m = f m best . 3. Select set of p = m -k shifts (µ (m) 1 , . . . , µ (m)
p ), based upon σ(H m ) or perhaps other information and set q T ← e T m . 4. For j = 1, . . . , p

• Factor [Q j , R j ] = qr(H m -µ (m) j I); • H m ← Q H j H m Q j ; V m ← V m Q j , • q ← q H Q j 5. Set f k ← v k+1 β k + f m q(k), V k ← V m (1 : n, 1 : k), H k ← H m (1 : k, 1 : k) 6. Beginning with the k-step Arnoldi factorization AV k = V k H k + f k e T k , apply p i = m i -k additional steps of the Arnoldi process to obtain ℓ new m i -step Arnoldi factorization AV mi = V mi H mi + f mi e T mi (for i = 1, . . . , ℓ).
of orthogonalization may still dominant the computation when A is sparse and p is large.

Let CI and CM be the time complexities of one restart cycle of IRAM(m ℓ ) and MIRAMns(m 1 , • • • , m ℓ ) respectively. If we ignore terms not including n and the cost of stopping criterion, these complexities can be given by CI

= α + O 2 × n × m 2 ℓ and CM = α + O 2 × n × k × (m 1 + . . . + m ℓ ) + m 2
best -k × m best where α is the complexity of the common part of both algorithms. To compare these complexities, we can notice that in the worst case for MIRAMns where

m best = m ℓ , CM -CI = O (2 × n × k × (m 1 + . . . + m ℓ-1
)) which is positive and in the best case where

m best = m 1 , C M -C I = O 2 × n × k × (m 2 + . . . + m ℓ ) + m 2 1 -m 2 ℓ
which could be positive or negative. That means, according to the k and m i values, one restart cycle of MIRAMns could be less expensive than the one of IRAM. Consequently, MIRAMns(m 1 , • • • , m ℓ ) could be less expensive than IRAM(m ℓ ).

The space complexity of MIRAMns is O(n 2 + n × m ℓ ).

Parallelism analysis of MIRAMns .

The same parallel programming model as that one used in the implicitly restarted Arnoldi method can be used for the multiple implicitly restarted Arnoldi method with nested subspaces [START_REF] Maschhoff | An efficient portable large scale eigenvalue package for distributed memory parallel architectures[END_REF]. Then, the distributed parallel programming model defined and implemented in the library P ARPACK can be applied to MIRAMns also.

Nevertheless, it should be noted that MIRAM (with nested or non nested subspaces) has a great potential for large coarse grain parallelism among its Arnoldi factorizations. Indeed, the computation in different subspaces of MIRAM could be done in parallel. In addition to this coarse grain parallelism among IRAM processes, one can also overlap communication step with computations. Indeed, the communication of the eigen-information of interest of each IRAM process to other IRAM processes can be done asynchronously. The analyse of intra and inter Arnoldi factorizations parallelism in MIRAM and its implementations on large scale distributed systems can be the subject of a future work.

Suggestion to set subspace sizes.

As already stated, a too small value for the size of the subspace would lead to non-appearance of eigen-information of interest in the subspace. Moreover, the choice of a too large value for this parameter could lead to an excessive the computation cost for orthogonalization process of mstep Arnoldi factorization. Therefore, a compromise between a too large value and a too small value for m is required. Setting this value is very much problem dependent. Indeed, it is selected empirically depending on the size of the problem, the number of desired eigenvalues/eigenvectors, etc. As a rule of thumb m 2 × k is suggested by [START_REF] Sorensen | Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations[END_REF][START_REF] Lehoucq | ARPACK User's Guide: Solution of Large Scale Eigenvalue Problems With Implicitly Restarted Arnoldi Methods[END_REF] as a reasonable choice. It is good to notice that m = 2k is the default in Matlab. It is also suggested, where possible, to avoid setting k in a way that will split clusters of eigenvalues. As a result, this is true for the choice of m as well.

Let [m 1 , • • • , m ℓ ] be the discrete interval of subspace sizes in MIRAMns. The lower bound m 1 should be chosen small enough to provide good orthogonality of basis vectors of Krylov subspace. Applying the rule of thumb described above is a acceptable choice (i.e.: m 1 2 × k). The upper bound m ℓ should be large enough so that the Krylov subspace can contain all the required eigenvalues. We choose the values within this range distributed fairly uniformly.

The technique presented here is a way to make better the size of the subspace in Arnodi restarted methods. This approach allows improving the quality of the Krylov subspace K m,v by the refinement of the parameter m at the same time as that of the parameter v by these restarted methods. Nevertheless, the approach belongs empirical and could be improved by analyzing the results of intensive experimentation. In all experiments presented here, initial vector is x = z n / z n 2 except for the Figure 5.8(a) that initial vector is x = s n / s n 2 and the Figures 5.9(a) and 5.10 that initial vector is x = t n / t n 2 where

z n = (1, 1, • • • , 1) T , s n = (1, 1, 0.1, • • • , 0.1) T and t n = (1, 1, 0, • • • , 0) T .
The initial vectors of IRAM and MIRAMns are the same. The efficiency of these algorithms can thus be measured in terms of the number of restarts cycles (nrc) or the number of matrix-vector products M V P . Our matrices are presented in the table 5.1.

We have used four matrices af 23560.mtx, bf w782a.mtx, west0989.mtx and sher-rman3.mtx from Matrix Market [START_REF] Bai | A Test Matrix Collection for Non-Hermitian Eigenvalue Problems[END_REF]. A9 1000 is a tridiagonal matrix of order 1000 defined by a i,i = 3 , a i,i+1 = a i,i-1 = 1. All other entries are zero. The tridiagonal matrix AM 1000 is of dimension n = 1000. The diagonal entries are a i,i = i, the codiagonal entries are a i,i+1 = -0.1 and a i,i-1 = 0.1. All other entries are zero. This example has been taken from [START_REF] Morgan | On Restarting the Arnoldi Method for Large Nonsymmetric Eigenvalue Problem[END_REF]. Matrices roadNet-PA.mtx, com-Youtube.mtx and W ikiT alk.mtx are transition matrices constructed from three social graphs by using Markov chain. These graphs could be found in [ ), IRAM(m) denotes an IRAM with subspace size m and M V P denotes the number of matrix-vector products. It is important to note that the main objective of our experiments is to compare the performance of MIRAMns(m 1 , • • • , m ℓ ) and IRAM(m ℓ ). However, some of experiments have the aim of highlighting the influence of certain parameters on the convergence of these methods. For some typical cases, we present the best subspaces choosen by MIRAMns throughout the restarting cycles, so as to clarify the necessity of using the whole set of subspaces.

The table 5.2 presents the results obtained with IRAM algorithm and the table 5.3 presents the results obtained with MIRAMns and a comparison between IRAM and MIRAMns in term of number of matrix-vector products (M V P ), execution time in seconds (Ex.T ime) and number of restarts (nrc). Ex.T ime represents the total execution time: from the beginning of the algorithm (after inputs) upto obtaining the wanted eigenpairs. We can see that in almost half of the experiments presented in table 5.2, IRAM does not converge. The results presented in the table 5.3, show that MIRAMns overcomes these problems of non-convergence.

We show graphically in Figures 5.1 to 5.10 the norm of residual as a function of restart cycle number to reach convergence using MIRAMns and IRAM. We see that there is no convergence for IRAM in figures 5.1 to 5.5, 5.9(a) and 5.10 while MIRAMns reaches convergence. Moreover, the convergence of MIRAMns in figures 5.7, 5.8, 5.9(b) and 5.12(a) is better than IRAM. Specifically, Figure 5.1(a) shows that the curves of convergence of IRAM and MIRAMns undergo oscillations around the residual norm 10 -6 . However, the peak to peak amplitude of the oscillations corresponding to IRAM is very large while the one corresponding to MIRAMns are quite small. This could become related to a kind of smoothing of the curve of convergence of IRAM by MIRAMns.

Figure 5.1(b) shows the influence of the size of the subspace on the convergence of IRAM. Indeed, we note that an augementation of this size relative to that of Figure 5.1(a) smooths the curve of the convergence of IRAM. We can see also that with the chosen tolerance (tol = 10 -8 ), MIRAMns converges but IRAM does not converge. However, with a greater tolerance value such as tol = 10 -7 , IRAM reaches convergence when MIRAMns does not reach it. But it must be remembered that in this case, the parameters of IRAM and MIRAMns no longer meet the criteria for comparison. Indeed, the subspace size of IRAM [START_REF] Sorensen | Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations[END_REF] is larger than m l = 10. Figure 5.1(a) shows the effect of increasing the size of the subspace on the convergence of IRAM and MIRAMns and highlights the speed of convergence of MIRAMns with respect to that of IRAM. The acceleration of convergence of IRAM by MIRAMns is also shown in Figures 5.4 to 5.10. However, we can see that in Figure 5.4(a), before tol = 10 -5 , IRAM could reach convergence faster than MIRAMns. But this is just an oscillation peak stronger than the others and the residual norms do not decrease continually while those of MIRAMns decreases steadily during the restart cycles. Figures 5.4 and 5.10(b) show further how the convergence curves of IRAM are "smoothed" by MIRAMns. Furthermore, by comparing subfigures in Figure 5.2 and Figure 5.5, we notice that an increase in number of subspaces could improve the speed of convergence for MIRAMns itself as well.

Figures 5.11 and 5.12(b) show the subspaces selected by MIRAMns throughout restart cycles. We see that m best is choosen randomly from interval [m 1 , m l ] and for some experiments m 1 is selected as best subspace size more often that m l (Figure 5.11(b)). This phenomenon of local optimality of small subspaces was also observed by Embree on GMRES [START_REF] Embree | TheTortoise and the Hare Restart GMRES[END_REF]. Figures 5.13 and 5.14 show the execution time of MIRAMns versus IRAM throughout restart cycles for AM 1000 and west0989 matrices. We notice that the execution times of each restarting cycle is almost the same for both methods. Nevertheless, the total execution time of MIRAM is much smaller than IRAM.

Tables 5.2 and 5.3 and Figures 5.1 to 5.10 indicate that our algorithm improves performances of IRAM. We notice also that this improvement is much more significant when the matrices have clustered eigenvalues such as af 23560 and bf w782 matrices used in our experiments.

MIRAMns versus other approches.

To check the influence of the strategy proposed by Stathopoulos, Saad and Wu in [START_REF] Stathopoulos | Dynamic Thick Restarting of the Davidson, and the Implicitly Restarted Arnoldi Methods[END_REF], we compared the tick restarted versions of IRAM and MIRAMns. The Figures 5.6 shows this comparison with the number of wanted eigenpairs k = 15 and the thick parameters 2 and 5. That means in each restart cycle, a buffer of 2 and 5 extra vectors are kept. We can notice that IRAM could sometimes perform as good as MIRAMns.

Figure 5.15 shows the results of comparison with DIRA, the method proposed by Dookhitram et al. in [START_REF] Dookhitram | A new method for accelerating Arnoldi algorithms for large scale Eigenproblems[END_REF]. The matrix, initial vector and tolerance value are bf w782a, x = t n / t n 2 and 10 -10 respectively. Figure 5. 15(a) shows that MIRAMns reaches convergence in 8 restarting cycles while DIRA converges in 12 cycles. The execution times of MIRAMns and DIRA are 0.045 and 0.08 seconds respectively. Figure 5 6. Conclusion. Due to the empirical choice of subspace size, the implicitly restarted Arnoldi method may not be efficient for computing a few selected eigenpairs of large sparse non-Hermitian matrices. In order to improve this choice, we have proposed to make use of this method with several Krylov subspaces. We have seen that the multiple implicitly restarted Arnoldi method with nested subspaces accelerates the convergence of IRAM with the same number of matrix-vector products in each restart cycle. Our numerical experiments have shown that MIRAMns improves the quality of the Krylov subspaces of IRAM and has consequently better convergence properties. Moreover, the strategy presented in the paper can be applied to many other restarted projection methods. In a general context, this is equivalent to coupling some iterative methods in order to accelerate the convergence of one of them as is the case of hybrid Arnoldi-Chebyshev method described in [START_REF] Chatelain | Eigenvalues of matrices[END_REF][START_REF] Saad | Chebyshev Acceleration Techniques for Solving Nonsymmetric Eigenvalue Problems[END_REF]. We mentioned that for MIRAMns we can use the same parallel programming model as the one used in P ARPACK [START_REF] Maschhoff | An efficient portable large scale eigenvalue package for distributed memory parallel architectures[END_REF] which implements the parallel implicitly restarted Arnoldi method. An implementation of MIRAMns within ARPACK is given in the following URL: (https://forge.prism.uvsq.fr). This is because we define a Krylov subspace and make use of the eigen-information of some subspaces nested in it. Another approach consists to make use of IRAM with several Krylov subspaces which differ by both their initial vector and subspace size. This approach, multiple IRAM, has the advantage to update (implicitly) the initial vector of an IRAM by taking into account the eigen-information obtained by several different (non nested) subspaces. The increase cost engendered by these different subspaces could be compensated by the implementation of the method in a large-scale distributed environment as for the multiple explicitly Arnoldi method in [START_REF] Emad | Multiple Explicitly Restarted Arnoldi Method for Solving Large Eigenproblems[END_REF].

  be an orthogonal basis of this subspace generated by the Gram-Schmidt orthogonalization process. A relation of the form

  m) i | is the residual norm associated to this Ritz eigenpair. The number |β m e T m y (m) i | is called also Ritz estimate where β m = f m 2 . In the rest of this paper, we denote by k the number of wanted eigenvalues, by {µ (m) i } p i=1 the set of unwanted eigenvalues of H m (p = m -k), by A F the Frobenius norm of A, by H m (1 : k, 1 : k) the leading k × k submatrix of H m and by nrc the number of restart cycles.

5 .

 5 Numerical experiments. We have implemented and tested Algorithm 1 (IRAM) and Algorithm 2 (MIRAMns) using MATLAB to compute k = 2 eigenvalues of greatest magnitude, except for certain case where convergence is too fast for both IRAM and MIRAMns. The stopping criterion used in IRAM is r m k = max(ρ m 1 , . . . , ρ m k ) < tol with ρ m i = |β m e T m y (m) i |/ A F where tol specifies the accuracy requested. The criterion used to select the best subspace size in MIRAMns is r m best k = min(r m1 k , . . . , r m ℓ k ) where m 1 < • • • < m ℓ are subspace sizes (with m 1 ≥ 2×k). Every other stopping criterion can replace the requirement to find k eigenvalues. The tolerance value tol is 10 -8 for the Figures 5.1 to 5.4(a), 5.7(a), 5.8; 10 -10 for the Figure 5.6(a); 10 -12 for the Figures 5.10 and 10 -14 for the Figures 5.4(b), 5.5, 5.7(b) and 5.9.

Fig. 5 . 1 :Fig. 5 . 2 :

 5152 Fig. 5.1: MIRAMns(5, 7, 10) versus IRAM(m) with af 23560 matrix

20 Fig. 5 . 3 :Fig. 5 . 4 :

 205354 Fig. 5.3: MIRAMns(m1, . . . , m ℓ ) versus IRAM(m) with bf w782a matrix

Fig. 5 . 5 :

 55 Fig. 5.5: MIRAMns(m1, . . . , m ℓ ) versus IRAM(m) with A9 1000 in (a), west0989 in (b)

10 Fig. 5 . 6 : 4 Fig. 5 . 7 : 10 Fig. 5 . 8 :Fig. 5 . 9 :Fig. 5 . 10 :

 1056457105859510 Fig. 5.6: MIRAMns(m1, . . . , m ℓ ) versus IRAM(m) with AM 1000 in (a), sherman3 in (b)

Fig. 5 . 11 :Fig. 5 . 12 :

 511512 Fig. 5.11: MIRAMns(13,[START_REF] Saad | Numerical Methods for Large Eigenvalue Problems[END_REF][START_REF] Saad | Numerical Solution of Large Nonsymetric Eigen Problem[END_REF] versus IRAM[START_REF] Saad | Numerical Solution of Large Nonsymetric Eigen Problem[END_REF] for AM 1000 matrix, tol=10-8

5 Fig. 5 . 13 :

 5513 Fig. 5.13: MIRAMns(m1, . . . , m ℓ ) versus IRAM(m) with af 23560 matrix, k = 10 with a buffer of q extra vectors

Fig. 5 . 14 :

 514 Fig. 5.14: MIRAMns(m1, . . . , m ℓ ) versus DIRA(m) with k eigenvaluesXXX

Table 5 .

 5 26]. 1: General information about the test matrices 5.1. MIRAMns versus IRAM. In all the following figures MIRAMns(m 1 , • • • , m ℓ ) denotes an MIRAMns with subspace sizes (m 1 , • • • , m ℓ

	Matrix	Size of matrix nonzero elements
	af 23560.mtx	23560	484256
	bf w782a.mtx	782	7514
	A9 1000.mtx	1000	2998
	west0989.mtx	989	3537
	AM 1000.mtx	1000	2998
	sherman3.mtx	5005	20033
	roadNet-PA.mtx	1088092	3083796
	com-Youtube.mtx	1134890	2988374
	W ikiT alk.mtx	2394385	5046614

  .15(b) shows the convergence of MIRAMns and DIRA in 19 and 67 restarting cycles. Their execution times are 0.19 and 0.25 seconds respectively. According to our experiments MIRAMns gives good results with respect of this approach.

	Matrix	m	x	tol	nrc	M V P	Ex.Time	Res.Norm	Fig.
	af 23560.mtx	10	zn	10 -8	* 500	*4002	10.27	no conv.	5.1 (a)
	af 23560.mtx	22	sn	10 -8	* 500	*10002	31.44	no conv.	5.1 (b)
									5.2
	af 23560.mtx	25	zn	10 -8	6	140	0.60	2.60e-09	5.12 (a)
	af 23560.mtx	40	zn	10 -10	114	2865	24.02	8.24e-11	5.6 (a)
	bf w782a.mtx	10	zn	10 -8	* 500	*4002	1.00	no conv.	5.4 (a)
	bf w782a.mtx	20	zn	10 -14	* 500	*9002	2.18	no conv.	5.4 (b)
									5.5
	bf w782a.mtx	30	zn	10 -14	12	195	0.09	1.98e-15	5.6 (b)
	A9 1000.mtx	20	zn	10 -8	309	5564	1.40	9.57e-09	5.7 (a)
	west0989.mtx	10	zn	10 -8	53	426	0.11	2.75e-09	5.7 (b)
	AM 1000.mtx	20	sn	10 -8	22	398	0.12	8.93e-09	5.8 (a)
	sherman3.mtx	10	zn	10 -8	4	34	0.04	5.40e-13	5.8 (b)
	roadNet-PA.mtx	20	tn	10 -14	* 500	*9002	1680.24	no conv.	5.9 (a)
	com-Youtube.mtx	20	sn	10 -14	30	482	113.20	3.03e-15	5.9 (b)
	W ikiT alk.mtx	20	zn	10 -12	* 500	*9002	4487.15	no converge	5.10

Table 5 .

 5

					2: IRAM performances
					IRAM		MIRAMns
	Matrix	Fig.	ℓ	m	nrc	M V P	m1, • • • , m ℓ	it	M V P	Ex.Time
		5.1 (a)	3	10	* 500	* 4002	5, 7, 10	272	2178	7.84
		5.1 (b)	3	22	* 500	* 10002	5, 7, 10	250	2002	7.88
	af23560	5.2 (a)	3	22	* 500	* 10002	16, 19, 22	31	622	2.68
		5.2 (b)	5	22	* 500	* 10002	10, 13, 16, 19, 22	8	162	0.82
		5.12 (a)	3	25	6	140	5, 10, 25	6	140	0.63
		5.6 (a)	3	40	114	2865	20, 30, 40	26	665	5.83
		5.4 (a)	3	10	* 500	* 4002	5, 8, 10	70	562	0.13
	bfw782a	5.4 (b)	3	20	* 500	* 9002	5, 10, 20	104	1874	0.32
		5.5 (a)	3	20	* 500	* 9002	8, 18, 20	92	1658	0.38
		5.5 (b)	5	20	* 500	* 9002	8, 11, 14, 17, 20	32	578	0.16
		5.6 (b)	3	30	12	195	20, 25, 30	14	225	0.13
	A9 1000	5.7 (a)	3	20	309	5564	10, 15, 20	94	1694	0.36
	west0989	5.7 (b)	3	30	53	426	5, 8, 10	32	258	0.07
	AM 1000	5.8 (a)	3	20	22	398	13, 17, 20	17	308	0.09
	sherman3	5.8 (b)	3	10	4	34	5, 8 , 10	2	18	0.02
	roadNet-PA	5.9 (a)	6	20	* 500	*9002	5, 8, 11, 14, 17, 20	157	2828	599.7
	com-Youtube	5.9 (b)	6	20	30	482	5, 8, 11, 14, 17, 20	20	332	108.08
	(k = 4)
	WikiTalk	5.10 (a)	6	20	* 500	*9002	4, 7, 10, 13, 16, 20	312	5618	3438.7
	(k = 2)
	WikiTalk	5.10 (b)	6	20	* 500	*9002	5, 8, 11, 14, 17, 20	15	272	181.5
	(k = 4)

Table 5 .

 5 3: Comparison of IRAM(m) and MIRAMns(m 1 , • • • , m ℓ )

	10	0	50	100	150	200	250	300	350	400	450	500


Tanay Agrawal
email: tanay.agrawal@inria.fr

Michal Balazia

Philipp Müller

Multimodal Vision Transformers with Forced Attention for Behavior Analysis

Human behavior understanding requires looking at minute details in the large context of a scene containing multiple input modalities. It is necessary as it allows the design of more human-like machines. While transformer approaches have shown great improvements, they face multiple challenges such as lack of data or background noise.

To tackle these, we introduce the Forced Attention (FAt) Transformer which utilize forced attention with a modified backbone for input encoding and a use of additional inputs. In addition to improving the performance on different tasks and inputs, the modification requires less time and memory resources. We provide a model for a generalised feature extraction for tasks concerning social signals and behavior analysis. Our focus is on understanding behavior in videos where people are interacting with each other or talking into the camera which simulates the first person point of view in social interaction. FAt Transformers are applied to two downstream tasks: personality recognition and body language recognition. We achieve state-of-the-art results for Udiva v0.5, First Impressions v2 and MPII Group Interaction datasets. We further provide an extensive ablation study of the proposed architecture.

Introduction

Human social behavior provides a wealth of information. For example, facial expressions are directly linked to emotions [START_REF] Erika | What the face reveals: Basic and applied studies of spontaneous expression using the Facial Action Coding System (FACS)[END_REF], and the pattern of eye contact in a group discussion has been shown to be indicative of leadership roles [START_REF] Capozzi | Tracking the leader: Gaze behavior in group interactions[END_REF][START_REF] Müller | Emergent leadership detection across datasets[END_REF]. Even the highly abstract concept of personality has been shown to be related to body pose [START_REF] Laura P Naumann | Personality judgments based on physical appearance[END_REF], gaze [START_REF] Hoppe | Eye movements during everyday behavior predict personality traits[END_REF][START_REF] Randy | Gaze avoidance: Personality and social judgments of people who avoid direct face-to-face contact[END_REF], and speech behavior [START_REF]Speech patterns and personality[END_REF]. With the goal to create machines that are able to interact more naturally with humans, significant efforts have been made to develop approaches that are able to sense and interpret human behavior across a wide range of scenarios and tasks [START_REF] Beyan | Prediction of the leadership style of an emergent leader using audio and visual nonverbal features[END_REF][START_REF] Beyan | Personality traits classification using deep visual activity-based nonverbal features of key-dynamic images[END_REF][START_REF] Liu | imigue: An identity-free video dataset for micro-gesture understanding and emotion analysis[END_REF][START_REF] Müller | Multimediate: Multi-modal group behaviour analysis for artificial mediation[END_REF][START_REF] Vinciarelli | A survey of personality computing[END_REF].

A major challenge for human social behavior analysis approaches is the large variability in human behavior. While a person's personality does play a role in their observable behavior, many other aspects such as turn-taking [START_REF] Birmingham | Group-level focus of visual attention for improved next speaker prediction[END_REF], leadership [START_REF] Beyan | Prediction of the leadership style of an emergent leader using audio and visual nonverbal features[END_REF], or rapport [START_REF] Müller | Detecting low rapport during natural interactions in small groups from non-verbal behaviour[END_REF] are likewise major influences and the contributions of different factors are difficult to disentangle. This issue is exacerbated by the small scale of available datasets. Especially modern transformer-based architectures that were applied successfully to a variety of tasks [START_REF] Akbari | VATT: transformers for multimodal self-supervised learning from raw video, audio and text[END_REF][START_REF] Liu | Video swin transformer[END_REF][START_REF] Vaswani | Attention is all you need[END_REF] struggle with such small datasets.

In this work, we introduce the novel Forced Attention (FAt) transformer which is fit for the unique challenges present in human behavior sensing and analysis. Figure 1 shows the architecture of the main branch. The FAt transformer addresses the problem of large behavior variability directly by attending to important parts and reducing noise in the input. The small dataset problem is addressed implicitly as a result of faster convergence. In detail, we introduce three distinct improvements to transformer-based human behavior analysis architectures.

First, we introduce a novel forced attention mechanism that is able to focus the processing on the relevant part of the input. Social interaction videos usually contain a single person who is relevant to the output task interacting with someone or something. The remaining part is background which contains potentially misleading information. We provide the spatial localization of the target person via a segmentation map to the network, thereby forcing the network to not attend to the background. Since the background might have important information, we observe that the network learn to assign attention to parts in the background that are also relevant to the provided background.

Second, we introduce a 2D patch partition layer in our model which combines the advantages of transformers with the robustness of convolutional layers. We observe that training models with fully-transformers based architectures results in difficulties, such as hard to converge, due to sensitivity to background noise and the requirement of a large training sample set. Instead, we break the videos into chunks and extract features per chunk using convolutional layers which makes the network less susceptible to pick up on noise (non-aligned frames and random transformations such as stretching) as the convolution operation is known to be more transformation invariant as compared to attention. Extracting features from chunks allows the input to retain its spatial structure as features are only extracted from local patches without changing their arrangement.

Finally, integration of multimodal data is crucial for complex human behavior analysis tasks. Cross-attention applied on the feature level in transformers was shown to offer effective multimodal integration for several tasks including emotion recognition [START_REF] Delbrouck | A transformer-based joint-encoding for emotion recognition and sentiment analysis[END_REF], personality recognition [START_REF] Palmero | Context-aware personality inference in dyadic scenarios: Introducing the udiva dataset[END_REF], and multi-view video recognition [START_REF] Shen Yan | Multiview transformers for video recognition[END_REF]. We introduce a novel variant of cross-attention in transformers which provides an optimised way to add multiple secondary inputs to one attention module.

We evaluate our model on two different human behavior analysis tasks: personality recognition (high level analysis) and body language recognition (low level analysis). We choose personality recognition, as it is a key task in social signal processing [START_REF] Vinciarelli | A survey of personality computing[END_REF] that exemplifies the challenges faced in social behavior analysis: a non-trivial association between behavior and ground truth with random influences along with small sizes of available datasets [START_REF] Hugo Jair Escalante | Modeling, recognizing, and explaining apparent personality from videos[END_REF][START_REF] Palmero | Context-aware personality inference in dyadic scenarios: Introducing the udiva dataset[END_REF]. Personality of a person is represented as a point in the so-called OCEAN space defined by the following five axes: O: Openness, C: Conscientiousness, E: Extroversion, A: Agreeableness, and N: Neuroticism. In addition, we evaluate our model on body language recognition, i.e. the recognition of classes of behavior such as "fumbling", "gesturing", or "face touching". In contrast to common action recognition tasks, body language recognition has a larger stochastic component as a result of more subjective annotation. We achieve state-of-the-art results on three realistic human interaction datasets. These include Udiva v0.5 [START_REF] Palmero | Context-aware personality inference in dyadic scenarios: Introducing the udiva dataset[END_REF] and First Impressions v2 [START_REF] Hugo Jair Escalante | Modeling, recognizing, and explaining apparent personality from videos[END_REF] for personality recognition, and MPII Group Interaction (MPIGI) [START_REF] Balazia | Bodily behaviors in social interaction: Novel annotations and state-of-the-art evaluation[END_REF] for action recognition. We provide extensive ablation experiments to evaluate the importance of our contributions.

To summarize, the field of behavior analysis in group interactions has multiple tasks. Previous approaches work well for a particular task, adhering to its intricacies. Our aim is to introduce a generalised feature extractor which can be easily modified for a chosen downstream task. Our contributions are the following:

1. We introduce the Forced Attention (FAt) mechanism which utilises segmentation maps to focus on relevant information in the input. The novelty is not in its computation, but in the way the segmentation map is incorporated in the attention mechanism of the transformer.

2. We propose an addition to Video Swin transformers. We extract features from patches of the input using a CNN based backbone making the model more robust.

3. We introduce a novel cross-attention module consisting of one main modality along with multiple other modalities.

Related Work

In the field of computer vision, CNNs have long shown to work well and have been used as backbone architectures. For tasks pertaining to videos, 3D models [START_REF] Carreira | Quo vadis, action recognition? A new model and the kinetics dataset[END_REF][START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF][START_REF] Tran | A closer look at spatiotemporal convolutions for action recognition[END_REF][START_REF] Qiu | Learning spatiotemporal representation with pseudo-3d residual networks[END_REF][START_REF] Xie | Rethinking spatiotemporal feature learning for video understanding[END_REF] have shown to give good results. But these approaches are limited by the small size of kernels with respect to the input. This is answered by vision transformers, which have a bigger receptive field with fewer parameters and have shown to have superior performance recently. Number of parameters is important for multimodal approaches as already the input requires a lot of memory. Vision Transformer (ViT) [START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] initialised the leaning of the community towards transformer based approaches. Video Swin Transformer [START_REF] Liu | Video swin transformer[END_REF], our baseline model, uses spatio-temporal local attention with spatio-temporal locality bias which has shown to perform well on various video related tasks. But its training is hard as it requires a large amount of data for converging which is presently not available for the tasks we are tackling. Owing to the specificity of our domain, there are some intricacies that we can exploit. Previous works, including our baseline, are not modified for these.

Since all input videos in this domain have interlocutors sitting in roughly fixed places in the frame and the cameras are also fixed, we utilise the best of CNNs and transformers to alleviate the problem of lack of data by using a CNN backbone on large local patches (28x28 or 112x112) of the input. The patches generally have similar information across time which is easy for CNN filters to learn on finetuning. The drawback attributed to CNNs of having a small receptive field is answered as the input itself is being broken into parts and fed in parallel. It also makes for a more robust model as CNNs converge faster and are known to work better for noisy data, thus providing a cleaner input to the transformers. The transformer based part applies attention over the concatenated output of this backbone providing embeddings for higher level features for behavior analysis. This is different from regular approaches which have a CNN backbone for the whole input followed by transformers.

As there is a lot of background noise in our tasks, we use foreground segmentation maps to provide the network with the information about which parts of the input to focus on. Since background is not to be completely removed from the input, providing the network with this information is not a trivial task. Previous works introduce a custom positional encoding for transformers which has a significant impact on performance [START_REF] Bao | Unilmv2: Pseudo-masked language models for unified language model pre-training[END_REF][START_REF] Hu | Relation networks for object detection[END_REF][START_REF] Hu | Local relation networks for image recognition[END_REF][START_REF] Li | Hierarchical opacity propagation for image matting[END_REF][START_REF] Raffel | Exploring the limits of transfer learning with a unified text-to-text transformer[END_REF]. But there are other stages where this information could be added. We study different configurations to pass this information to the network and show a better method for adding information to transformers for our use case, which hopefully inspires others to do similarly.

The task of combining audio and text modalities with video is challenging as they are inherently very different from each other. VATT [START_REF] Akbari | VATT: transformers for multimodal self-supervised learning from raw video, audio and text[END_REF] uses early fusion, where they input everything together. Although the earlier the fusion, the better the results, there is a trade-off with the amount of data required for training as it is harder for models with early stage fusion to converge which leads to tedious selfsupervised learning. Some works design a specialised architecture for fusion at feature level [START_REF] Agrawal | Multimodal personality recognition using cross-attention transformer and behaviour encoding[END_REF][START_REF] Palmero | Context-aware personality inference in dyadic scenarios: Introducing the udiva dataset[END_REF]. These work better but there are limitations as the fusion is done after downsampling the input features which leads to loss of information and poor cross-modality relations. [START_REF] Delbrouck | A transformer-based joint-encoding for emotion recognition and sentiment analysis[END_REF][START_REF] Kumar | Gated mechanism for attention based multimodal sentiment analysis[END_REF][START_REF] Shenoy | Multilogue-net: A context-aware rnn for multi-modal emotion detection and sentiment analysis in conversation[END_REF] have feature level fusion with minimal downsampling, but lack in handling specific modalities differently. To answer this, we introduce an architecture where each branch can benefit from separate pre-training and benefit from each other with feature level fusion using a custom cross-attention module. MViT [START_REF] Haoqi Fan | Multiscale vision transformers[END_REF] is a multi-scale vision transformer for video recognition trained from scratch that reduces computation by pooling attention for spatiotemporal modeling. We take their method of cross-attention as inspiration and extend it to be used with multimodal transformers. Dyadformer [START_REF] Curto | Dyadformer: A multi-modal transformer for long-range modeling of dyadic interactions[END_REF], which is the previous state-of-the-art for the UDIVA v0.5 dataset, uses only two modalities in each branch which leads to loss of information present in the relations among the secondary inputs. Our proposed cross attention module allows to use all modalities to be incorporated into the main branch together while including these relations.

In the next section we explain the methodology for implementing each of the above mentioned contributions.

Proposed Methodology

Input to the Model and the Different Branches

There are multiple input modalities and each of them have their own branches for processing before they are combined together using cross-attention which is discussed in Section 3.3. For the body language recognition task, the inputs are face crop sequence, full frame sequence of the target person, and audio of the conversation. For the personality recognition task, we also have full frame sequence of the interlocutor and transcript of the target person.

Face crop sequence is treated as the main input and the other modalities are merged into it. This is because it has been established that face crops have the most relevant information for affective computing and we show that it is extendable to group interaction behavior analysis. We extract face crop coordinates using OpenFace [START_REF] Baltrusaitis | Openface 2.0: Facial behavior analysis toolkit[END_REF] and take crops from the original full frame. This leads to some problems as the position of the face in subsequent faces may be different and after resizing and combining back to make a video, there is a lot of distortion as discussed in Section 1. This urged us to devise a way to handle them. The distortions in this branch include stretching and translation as the face crops are of different resolutions and they have to be resized to the input size of 224x224. We do not use aligned face crops from OpenFace to reduce dependence on other algorithms. We break the input into 112x112 patches and pass them through a 3d convolutional backbone, R(2+1)D (with some layers removed) and concatenate the output back again. The rest of the branch is based on Video Swin Transformers [START_REF] Liu | Video swin transformer[END_REF] with our contributions added to it and is discussed later.

The full frame sequence branch has similar processing as the face branch: it is broken into 64 chunks and passed through the same convolutional backbone with shared weights. The rest of the branch is Video Swin Transformer T [START_REF] Liu | Video swin transformer[END_REF].

The audio is passed through a pretrained model, Trill-Distilled [START_REF] Shor | Towards learning a universal non-semantic representation of speech[END_REF], which is not finetuned. The obtained embedding is used as input to the cross-attention module discussed in Section 3.3.

The transcript branch is similar to the audio one. The only difference being the model used to extract features is XLM-RoBERTa [START_REF] Conneau | Unsupervised cross-lingual representation learning at scale[END_REF].

Forced Attention

Transformers are known to be hard to train and due to the limited amount of data in the chosen domains, we choose to force the attention using foreground segmentation maps. As the background does not have relevant information, it does not have to be attended to. There are multiple ways to provide the model with this information. Adding the information encoded in the form of positional encodings is the most common way [START_REF] Bao | Unilmv2: Pseudo-masked language models for unified language model pre-training[END_REF][START_REF] Hu | Relation networks for object detection[END_REF][START_REF] Hu | Local relation networks for image recognition[END_REF][START_REF] Raffel | Exploring the limits of transfer learning with a unified text-to-text transformer[END_REF][START_REF] Li | Hierarchical opacity propagation for image matting[END_REF]. We study different ways and find a more suited approach to provide the model with this information. Figure 2 shows the different techniques and they are explained below. We choose to show all methods that we tried here so that it can help others working on something similar.

The first way which is the most common is to add an additional positional encoding. It is shown in Figure 2(a). Transformers need positional encoding to know the location of the tokens for attention. We added another encoding to the existing ones in Swin transformers. The encoding is based on a matrix, M 1 of size: Nc x E, where Nc is the number of chunks (refer to Video Swin transformers [START_REF] Liu | Video swin transformer[END_REF] for details) and E is the dimension of the embedding to which the encoding has to be added. The matrix is dynamic depending on the input. Figure 3 shows how the segmentation map is used to obtain this matrix. It is an array of ones of the size E if the chunk has pixels from the foreground or zeros otherwise. This matrix is by a weight array, W 1 to get the desired shape (E in this case) and added to the input.

X = X + SinusoidalPosEncoding+

ForcedAttentionPosEncoding

(1)

ForcedAttentionPosEncoding = W 1 * X (M 1 ) (2)
X is a sampler function that returns an embedding of size E from the matrix M 1 corresponding to the chunk that is needed. Figure 3 shows how the segmentation map is broken into parts and this function is needed to extract the required chunk for equation 2.

The second way we tried was to add a bias to the last linear layer in an attention module. This is shown in Figure 2(b). The bias is multiplied by one if the chunk has foreground pixels, otherwise by zero. If the bias is termed as B forced , we can write the linear layer's output as

Output = Linear (softmax (Q * k T )/ √ d) * V +X) + B forced (3)
B forced = LearnedBias * W 2 * X (M 1 ) (4)
Since attention is applied on input patches and encoders have the same input and output size, the same matrix can be utilised as the first approach. W 2 is used to change the size of chosen embedding from M 1 to the desired shape when required in later layers. The third way was to add the segmentation mask as another channel in the input and use a 1d convolution layer to reduce the number of input channels back to three. This method is straight forward and does not require much explanation. It is shown in Figure 2(d).

In the fourth approach that we took, we add the segmentation mask to the input multiplied by a learned parameter. It is shown in Figure 2(e).

X = (X * γ) + PositionalEncodings (5)
In the fifth, we add another bias similar to the first one but in the attention computation similar to 3D Relative Position Bias as in Video Swin Transformers [START_REF] Liu | Video swin transformer[END_REF]. It is shown in Figure 2(c).

Attention(Q, K, V ) = softmax (Q * k T + B Relative + B ′ forced / √ d) * V (6)
B ′ forced is calculated in a similar way to B forced . The only difference is that the shape is different and that is taken care by a linear layer.

The second approach gave the best results and is the one used for providing the results in the next section. We hypothesise that it is because it does not interfere with the local feature extraction from the patches but provides implicit global attention which materialises during the downsampling of channels during patch merging.

Cross-Attention Module

This is the module that allows us to augment the face crop branch with information from the other modalities. Cross-attention has gained popularity recently and has shown to work well but there are multiple ways of implementing it. Yan et al. [START_REF] Shen Yan | Multiview transformers for video recognition[END_REF] have a good comparison for some techniques and we utilise a modification of the approach that worked best for them and we extend it to use with multiple modalities to be added in one module.

In the third attention block of the face branch, we merge the modalities together. As shown in Figure 4, there are sequential cross-attention layers with full frame sequence and audio (and also transcript for personality recognition). We use 1d convolution for making the channel dimension of audio and transcript features equal to 768 which is the number of channels in the third attention block for the face crops sequence branch.

Cross attention is defined as the same as is the norm, we take the query as the main branch and the key and value as the side input.

For cross-attention with full frame sequence features, there is an additional cross attention layer after self- attention and also a residual connection imitating the selfattention layer. The parameters of this operation are zeroinitialised as this helps in using pretrained weights which is the common practice [START_REF] Bertasius | Is space-time attention all you need for video understanding?[END_REF]. For Udiva v0.5, there is another full frame sequence branch for the other interlocutor whose features added after the target person's as shown in Figure 4.

For cross attention with audio, the same approach is followed. With transcript and audio, two cross attention modules are added in place of one and both have recurrent connections along with another around both -the same as when two full frame sequences are present.

For faster processing, we use performer [START_REF] Choromanski | Rethinking attention with performers[END_REF] in place of traditional transformer attention. This might have lead to some performance loss, but it still serves as proof of concept and allows for more experiments with the available resources and time.

Classification Head

The outputs of the face crop and full frame sequence branches are of the shape B × C × D × H × W , where B is the batch size, C is the number of channels, D is the depth, H is the height and W is the width. Using an adaptive 3d pooling layer, it is reduced to B × C × 1 × 1 × 1 for each branch. The embeddings from each branch are concatenated along the channel dimension and then passed through a linear layer to get the output.

Experiments

Choice of Datasets

We choose two different tasks for experiments: personality recognition (high level) and body language recognition (low level). Since the work is focused on group interactions, the choice of datasets is done accordingly. For personality recognition, we use UDIVA v0.5 dataset which was a challenge for ICCV 2021. This is the biggest dataset available for this task. It contains dyadic interactions involving talking and playing games. We also give results on First Impressions v2 which is also a dataset for personality recognition where people are talking facing a camera. The dataset simulates first person point of view of interactions and is a good benchmark for personality recognition as it annotates YouTube videos containing people from a diverse background and the annotations are confirmed by multiple people, so they are less influenced by personal biases. For body language recognition, we choose MPIGI dataset [START_REF] Balazia | Bodily behaviors in social interaction: Novel annotations and state-of-the-art evaluation[END_REF]. It has 15 body language classes, such as "fumbling", "scratching", "arms crossed", "face touching", and "grooming". A more detailed description of the datasets is given in the supplementary material.

Training Details

We pretrain the full frame sequence branch on the Kinetics-400 dataset to reduce training time for the other datasets and to have a good initialisation as the other datasets are not equally big and transformers are known to be data hungry. We use the same configuration as in the Video Swin Transformer paper [START_REF] Liu | Video swin transformer[END_REF]: AdamW optimiser for 30 epochs with learning rate 3e-5 for the CNN backbone and 3e-4 for the rest of the parameters. The batch size is taken as 64. 0.1 stochastic depth rate and 0.02 weight decay are used. For the CNN backbone, R(2+1)D, we use pretrained weights with the network trained on IG65million [START_REF] Ghadiyaram | Large-scale weaklysupervised pre-training for video action recognition[END_REF] dataset.

For UDIVA v0.5, we use the above weights as initialisation for the full frame sequence branch. The CNN backbone is shared with the face branch. We set the learning rate for the CNN backbone and the full frame sequence branch as 3e-5 and for the remaining part of the face crop sequence branch as 3e-4. These are obtained from roughly scaling the one used in [START_REF] Liu | Video swin transformer[END_REF] from the tiny variant for Kinetics-400 1K according to the batch size (divide by square root of the ratio of batch sizes). The batch size is taken as 4. The initialisation of the face crop branch is inspired from [START_REF] Agarwal | From multimodal to unimodal attention in transformers using knowledge distillation[END_REF]. The shapes do not match from the full frame sequence and we need to reshape the weights to reuse them, so we use binning methods for reshaping as described in [START_REF] Agarwal | From multimodal to unimodal attention in transformers using knowledge distillation[END_REF].

For First Impressions v2, the configuration is the same as Udiva v0.5 except the fact that there is no second interlocutor so there is only one full frame branch. We also use some additional information for this dataset that is provided as metadata. We concatenate the information with audio and transcript and pass them through a linear layer to reshape into the original size.

For MPIGI dataset also, we do not use the information of the other interlocutor as the annotation for dyadic interaction is not available and having 3 or 4 branches for fullframe sequence is not viable due to space and time constraints. The learning rate used is double as compared to the others, i.e. 6e-4 and 6e-5 for respective parameters as explained for Udiva. Weight decay is set to 0.03. Rest of the hyperparameters remain the same. Due to imbalance of samples available for each class, we use oversampling for training samples with less frequency of occurrence and undersampling for the ones with very frequency and also a custom sampler for the dataloader which makes sure that the batches are not imbalanced.

Comparison with the State

-of-the-Art 4.3.1 UDIVA v0.5
Table 1 presents the results of state-of-the-art approaches on Udiva v0.5. Our approach greatly outperforms the previous approaches. We use the same metric that is used for the challenge, mean squared error averaged over participants. There is an interesting pattern that we saw in our experiments as compared to the others. We got better results for a few classes upon training for more epochs, but worse mean error. So, using an ensemble of trained models would give better results, but we leave that for future work. Another difference between our approach and the others is the choice of not using metadata. Other approaches use it extensively. Despite further performance improvements, we prefer a more generalised approach and so we choose to avoid the metadata, gaze and pose features. This is the reason that we hypothesise for having worse results for the Agreeableness class than hanansalam in Table 1. Their approach uses separate branches for male and female participants and due to data bias, it may be easy for the model to predict Agreeableness when there is a separation on its basis. But overall, we show that our model outperforms previous approaches for personality recognition in dyadic interaction videos. We do not include one paper that has the best results after us on this dataset as they do not provide results for individual classes for their best configuration. They achieve a mean error of 0.722 using the same data along with metadata about the participants which gives them a big boost. We manage to achieve a score of 0.706 with the metadata, training for only 4 epochs. The improvement is statistically significant as the 95% confidence interval for MSE on UDIVA dataset is 0.036. [START_REF] Güc ¸lütürk | Deep impression: Audiovisual deep residual networks for multimodal apparent personality trait recog-nition[END_REF] 0.912 0.911 0.911 0.916 0.909 0.912 Evolgen [START_REF] Subramaniam | Bi-modal first impressions recognition using temporally ordered deep audio and stochastic visual features[END_REF] 0.913 0.914 0.915 0.916 0.910 0.914 Gurpinar et al. [START_REF] Gürpinar | Multimodal fusion of audio, scene, and face features for first impression estimation[END_REF] 0.914 0.914 0.919 0.914 0.912 0.915 PML [START_REF] Salah Eddine Bekhouche | Personality traits and job candidate screening via analyzing facial videos[END_REF] 0.914 0.917 0.918 0.917 0.913 0.917 BU-NKU [START_REF] Kaya | Multi-modal score fusion and decision trees for explainable automatic job candidate screening from video cvs[END_REF] 0.917 0.917 0.921 0.916 0.915 0.917 Agrawal et al. [START_REF] Agrawal | Multimodal personality recognition using cross-attention transformer and behaviour encoding[END_REF] 0.929 0.926 0.927 0.929 0.921 0.926 FAt transformer 0.942 0.951 0.955 0.949 0.959 0.951

First Impressions v2

Table 2 shows the results of the best previous works on this dataset. For this dataset also, we greatly outperform previous work. The approach in [START_REF] Agrawal | Multimodal personality recognition using cross-attention transformer and behaviour encoding[END_REF] uses cross-attention and fusion of different modalities at the feature level, but it loses a lot of information in down sampling before crossattention and we feel that our approach produces superior results compared to theirs because of this reason. We use the same metric for comparison that is used in other work:

Accuracy = 1 - 1 N N i=1 |t i -p i | (7)
where t i are the ground truth scores and p i are the predicted scores for personality traits summed over N videos.

MPII Group Interaction

Table 3 shows results of state of the art algorithms that we fine-tuned on MPIGI dataset [START_REF] Balazia | Bodily behaviors in social interaction: Novel annotations and state-of-the-art evaluation[END_REF]. We use accuracy and weighted average of F 1 -scores over the classes (weight depending on the number of samples for each class) as metrics. F 1 -score for each class is defined as the harmonic mean of the precision and recall for that action class. As the dataset is heavily imbalanced, accuracy alone would not have been a good metric. We outperform even a bigger variant of the baseline that we choose, video Swin transform-

Ablation Study

Main contributions

When segmentation map is absent from the input, we noticed that the model performance oscillates in every epoch.

In Table 4, we give results with the best mean validation score across the OCEAN classes. Due to the bias in the dataset and maybe even the personality classes, we saw that in a particular epoch the model performed well either on O, C and E classes together or A and N classes. In Table 4 for instance, it can be seen that the model does not perform well on A and N without (w/o) forced attention for the chosen epoch. We saw the same phenomenon in a separate experiment where we tried an approach similar to VATT [START_REF] Akbari | VATT: transformers for multimodal self-supervised learning from raw video, audio and text[END_REF] without contrastive learning. So, we conclude that forced attention indeed helps the model converge.

Without patch partitioning and a CNN backbone, the transformer behaves similarly with the exception of extroversion class. This corroborates our assumption that this contribution also helps in convergence.

Using only one side input and changing it in successive blocks in place of the proposed module allows the network to converge properly, but the performance across all classes decreases. This contribution allows our network to better exploit the correlations between the modalities and this ablation study supports the claim.

Late Fusion

We try two different configurations for the classification head using only features from the face branch, and with both full-frame and face crop sequence branches concatenated along the channel dimension. The latter one gave the best results, but they are not very different from using only face features which is the second row in Table 4. This shows that the cross-attention module incorporates the relevant information from the other branches (other than the face crop sequence) properly and this explains why late-fusion does not have a great impact on results.

Different Modalities

We show how the model works when audio and transcript inputs are missing. There is significant reduction in performance when either modality is missing which shows the importance of both. It can be seen that some classes are more affected by the absence of these modalities. Class A has the most reduction in performance, but this might also be explained by the fact that the model does not properly converge for this class and having more input modalities helps with that. On the other hand, results on C seems to be highly dependant on these modalities as the model is able to converge for this class in the forced attention ablation study, but not without these. These results also show that our architecture works well in merging information from audio and transcript into the face crop sequence.

Conclusion

We presented a method to efficiently incorporate multiple modalities into one model for human behavior analysis. Our model outperforms the state-of-the-art on three different datasets. Udiva v0.5 and First Impressions v2 tackle the high level problem of personality recognition while MPIGI tackles the low level problem of body language recognition. For the respective datasets, we achieve 0.050 lower MSE (ignoring dyadformer: described in detail in section 4.3.1), 1.3 % higher accuracy, and 3.6 % higher accuracy. Through ablation studies, we showed that each of our contributions has a significant impact on the performance of the model. We studied different ways to incorporate information in a transformer and show the impact of the one with the best performance through the visualisation of attention on an example input frame. We hope that this work inspires more work in this area as it is not widely explored.

FaceFigure 1 .

 1 Figure 1. Face branch of the model showing the contributions of our work. Overall architecture is provided in the supplementary material.

Figure 2 .

 2 Figure 2. Different stages of adding segmentation map for forced attention in transformer encoder. (a) shows addition of an additional positional encoding to the input with the original. (b) shows addition of a bias to the last linear layer of multi-head self attention module.(c) shows adding bias similar to 3D relative bias as in[START_REF] Bao | Unilmv2: Pseudo-masked language models for unified language model pre-training[END_REF][START_REF] Hu | Relation networks for object detection[END_REF][START_REF] Hu | Local relation networks for image recognition[END_REF][START_REF] Raffel | Exploring the limits of transfer learning with a unified text-to-text transformer[END_REF]. (d) shows segmentation map being concatenated as an additional channel to raw input and then being reduced back to original shape using Conv1D. (e) shows addition of segmentation map to each channel of the input.

Figure 3 .

 3 Figure 3. Visualisation of the operation to divide the segmentation map into patches to be used for input to the model in the form of the described matrix M1.

Figure 4 .

 4 Figure 4. Cross-attention for multiple side inputs.

Table 1 .

 1 MSE results for Udiva v0.5, as cited from the 2021 ICCV Understanding Social Behavior in Dyadic and Small Group Interactions Challenge: Automatic Self-Reported Personality Recognition Challenge https://chalearnlap.cvc.uab.cat/ challenge/45/track/43/result/ as of 29/08/2022.

	Model	O	C	E	A	N	Mean
	hanansalam	0.711 0.723 0.867 0.548 0.997 0.770
	juliojj [39]	0.744 0.794 0.886 0.653 1.012 0.818
	f.pessanha	0.752 0.687 0.917 0.671 1.098 0.825
	gizemsogancioglu 0.759 0.677 0.952 0.677 1.163 0.846
	FAt Transformer 0.668 0.624 0.730 0.590 0.987 0.720

Table 2 .

 2 Accuracy results for First Impressions v2.

	Model	O	C	E	A	N	Mean
	Aslan et al. [4]	0.917 0.921 0.921 0.919 0.916 0.919
	DCC

Table 3 .

 3 Accuracy and F1-score results for MPII Group Interaction.

	Model	Accuracy Weighted F 1 -Score
	TSN [51]	0.443	0.442
	TSM [32]	0.607	0.599
	Video Swin B [34] 0.656	0.637
	FAt Transformer 0.692	0.685

Table 4 .

 4 MSE results for Udiva v0.5 as ablation study.

	Model	O	C	E	A	N	Mean
	FAt Transformer	0.668 0.624 0.730 0.590 0.987 0.720
	w/o Forced Attention 0.705 0.704 0.873 0.966 1.264 0.902
	w/o CNN backbone 0.672 0.622 0.850 0.737 1.208 0.818
	w/o Cross Attention 0.813 0.776 0.794 0.619 1.118 0.824
	w/o Late Fusion	0.709 0.629 0.751 0.602 1.012 0.741
	w/o Audio	0.797 0.919 0.874 0.844 1.079 0.903
	w/o Transcript	0.839 0.876 0.832 0.760 1.150 0.911

ers

[START_REF] Liu | Video swin transformer[END_REF]

(we use Swin T and compare with Swin B) owing to our contributions which shows their saliency for this field. We also outperform other approaches that give state-of-theart results on action recognition which is the closest field to this dataset with numerous previous works.

Acknowledgments

This work was supported by French National Research Agency under the UCA JEDI Investments into the Future, project number ANR-15-IDEX-01, and by German Ministry for Education and Research, grant number 01IS20075.