Helen Callaghan
email: callaghan@mpifg.de

Paul Lagneau
email: paul.lagneau-ymonet@dauphine.fr

French governments are famous for promoting national champions, notably by preventing foreign takeovers, but in 2005-2006, the Villepin administration allowed the New York Stock Exchange to take control of Euronext, a French-led pan-European company that includes the Paris Bourse. By mapping the public discourse surrounding this striking case of non-intervention, we explain why opponents of the transatlantic merger failed in their appeals to "economic patriotism." Discursive strategies designed to justify discrimination against territorially defined outsiders ran into several hurdles, including weak patriotic sentiments for the company concerned; a lack of patriotic alternatives to the proposed merger; and the questionable patriotic credentials of those demanding intervention. Our findings advance research on the demand side of "economic patriotism," including its discursive dimension. Beyond that, they inform research on business-government relations, and on the political implications of corporate ownership structures.

Zusammenfassung

Französische Regierungen sind eigentlich dafür bekannt, dass sie einheimische Unternehmen vor Auslandsübernahmen schützen. Im Jahr 2005-2006 gestattete Villepins Regierung jedoch der New York Stock Exchange die Übernahme von Euronext, einer paneuropäischen Gesellschaft unter französischer Leitung, zu der auch die Pariser Börse gehört. Der öffentliche Diskurs zu diesem bedeutenden Fall von Nichtintervention gibt Aufschluss darüber, warum die Gegner der transatlantischen Fusion mit ihren Forderungen nach Wirtschaftspatriotismus scheiterten. Diskursiven Strategien zur Rechtfertigung von Diskriminierung gegen territorial definierte Außenseiter standen mehrere Hindernisse im Weg, etwa unzureichend ausgeprägte patriotische Gefühle für den Übernahmekandidaten, der Mangel patriotischer Alternativen zu einer transatlantischen Fusion und die mangelnde patriotische Glaubwürdigkeit derer, die eine staatliche Einmischung forderten. Der vorliegende Aufsatz ergänzt mit seinem diskursiven Schwerpunkt die aktuelle Forschung zu Wirtschaftspatriotismus. Außerdem trägt er zur Forschung über die Beziehungen zwischen Staat und Unternehmen und über die politischen Auswirkungen von Veränderungen in der Struktur von Unternehmenseigentum bei.

Introduction

The Paris stock exchange -located until the 1990s at the Palais Brongniart in the Opera district of the French capital -has over the past three decades changed in ways that seem difficult to reconcile with the dirigiste image of French governments. In 2006, after successive cross-border mergers, this former symbol of national economic sovereignty became a subsidiary of the New York Stock Exchange (NYSE). Four years later, Euro next Paris and other continental European entities of the now American-run group experienced significant downsizing and the relocation to London of crucial business units. 1 The relative weakness of political efforts to prevent the Paris stock exchange from falling into foreign hands is surprising, for several reasons. The cross-border merger took place in a country with a long-standing record of transatlantic defiance and of political intervention in the market for corporate control; it coincided with heavy-handed attempts to prevent cross-border mergers in other sectors of the French economy; it concerned a sector that is arguably of high economic and political significance and with regard to which the French government has formal legal instruments of intervention at its disposal. Why did the same government that took legislative action to prevent a rumored takeover of Danone, the French food conglomerate, by the American food and beverage giant PepsiCo, allow NYSE to gain control of Euronext? By mapping the public discourse surrounding this striking case of non-intervention, we explain why opponents of the transatlantic merger failed in their appeals to economic patriotism. Discursive strategies designed to justify political discrimination against territorially defined outsiders ran into several hurdles. Patriotic sentiments were difficult to mobilize for a company as perceivedly "Anglo-Saxon" as Euronext; the patriotic credentials of key opponents to the merger were weak, because many of them had prepared the ground by profitably selling their shares abroad; and instead of a patriotic alternative, "imperialist" advances by Deutsche Börse were seen as a likely outcome of failure to merge with NYSE.

Our findings advance research on economic patriotism by helping to explain when governments choose to discriminate in favor of territorially defined insiders. [START_REF] Clift | Economic Patriotism: Re-Inventing Control over Open Markets[END_REF] distinguish different kinds of state action used to defend local economic interests, but they do not offer any insights as to what determines whether governments act at all. Answering the latter question requires looking beyond the supply of state action to the demand side of economic patriotism, including its discursive dimension. Words often mask underlying material interests, but this does not mean that social scientists should discard them and strive only to look behind the smokescreen. As [START_REF] Bourdieu | Language and Symbolic Power[END_REF] notes, language is political action. In democracies, the supporters and proponents of state for investigating forms of government discrimination in favor of territorially defined insiders. Clift and Woll promote the term as more capable of capturing the wide range of instruments and strategies than other labels, such as "economic nationalism," "protectionism," or "neo-mercantilism." Unlike the former, "economic patriotism" can also refer to supranational or subnational economic citizenship. Unlike the latter two, it is not defined by its policy content and can thus also encompass deregulating policies, provided that they reflect economic partiality towards particular territorially defined groups.

While the heuristic provided by Clift and Woll usefully distinguishes different levels (supranational, regional, local), ideological affinities (liberal or conservative) and policy objectives (favoring insiders or resistance to outsiders) of economic patriotism, it does not offer any insights as to when politicians choose to privilege territorially defined groups. The case studies assembled in the special issue edited by Woll and Clift, which describe instances of economic patriotism in a variety of different contexts, do not provide sufficient leverage on this question. Answering it requires a closer look at cases in which political action was conspicuously absent.

The merger of Euronext with NYSE lends itself well because, a priori, there were strong reasons to expect political intervention. First, research on the geography of financial markets suggests that the location of stock markets has economic, regulatory and political implications. Economically, spatial proximity of issuers, investment banks, financial analysts, and asset managers to the stock market enhances the exchange of both formal and informal information and offers valuable network externalities. These benefits are said to explain why, contrary to predictions that information technology would spell the "end of geography" (O'Brien 1992), financial activities remain highly concentrated in a few financial centers [START_REF] Tadjeddine | The Location of Financial Activities: The Impact of New Technlogies and The Financial Crisis[END_REF][START_REF] Sassen | The Embeddedness of Electronic Markets: The Case of Global Capital Markets[END_REF][START_REF] Ansidei | Les centres financiers internationaux[END_REF]). The same benefits are also cited as a reason for the persistently strong so-called "home bias" in investment decisions: investors tend to hold, trade, and obtain superior returns from securities issued by companies that are "familiar" to them (see Wójcik 2009Wójcik : 1505Wójcik -1506Wójcik , 2007: 202): 202). 3 From a supervisory point of view, stock market location matters because governments and regulatory authorities have only limited influence outside their own jurisdiction. Stock market regulation affects the market for corporate control, corporate governance, and the protection of investors. The transfer of regulatory power over these matters to foreign institutions therefore implies a weakening of economic governance at the national level. Politically, nations throughout the history of capitalism have used the size and might of their financial centers as resources in the contest for geopolitical leadership [START_REF] Ferguson | The Cash Nexus: Money and Power in the Modern World, 1700-2000[END_REF][START_REF] Cassis | Capitals of Capital: A History of International Financial Centres, 1780-2005[END_REF]Cassis/Bussière 2005;[START_REF] Braudel | Le temps du monde: Civilisation matérielle, économie et capitalisme XVe-XVIIIe siècle[END_REF][START_REF] Weber | Stock and Commodity Exchanges [Die Börse[END_REF][START_REF] Weber | Stock and Commodity Exchanges [Die Börse[END_REF]. Even the rapid expansion, since the launch of the Euromarkets in the 1960s, of cross-border financial transactions outside incumbent exchanges was originally promoted by the US and the British governments to secure their financial supremacy at that time (Helleiner 1994).

Second, the weakness of political efforts to prevent foreign control of the stock market coincided with a string of high-profile interventions against attempted foreign takeovers of other French companies (see Callaghan 2009b). Building on a long tradition of dirigisme [START_REF] Shonfield | Modern Capitalism: The Changing Balance of Public and Private Power[END_REF][START_REF] Zysman | Governments, Markets, and Growth[END_REF][START_REF] Suleiman | Change and Stability in French Elites[END_REF][START_REF] Suleiman | L'âge d'or de l'État: Une métamorphose annoncée[END_REF] pull themselves together and press for the creation of a pan-European stock exchange" (Agence France-Press, June 19, 2006; this translation and all subsequent ones by the authors). The Parti Socialiste let it be known that it was "completely opposed to the merger" (AFP, December 20, 2006). Pierre Moscovici, international affairs spokesman for the Socialist Party (Parti Socialiste, PS) and Jean-Pierre Jouyet, Secretary of State for European Affairs at the time of the merger and chairman of the Financial Markets Authority since December 2008, declared ex post that they would have preferred a European solution. 5 At the local level, Jean-Paul Huchon, head of the Paris area regional assembly (région Ile de France), regarded the transatlantic merger as a "bad signal" (La Chaîne Info, June 9, 2006).

Despite these widespread reservations, and in contrast to simultaneous intervention in other cross-border mergers, French policy-makers chose not to use the full repertoire of legal and political tools to prevent NYSE from acquiring Euronext. Instead, both the French Financial Markets Authority and the French government remained neutral on the ownership question: provided that the operator of the exchange complied with the regulations, legal requirements, and governance amendments to assure formal equilibrium between European and American members of its board, the capital structure of the exchange would not matter. The French chief regulator, Michel Prada, and his peers from the UK, Belgium, the Netherlands, and Portugal cooperated with their counterparts from the US Securities and Exchange Commission to solve legal technicalities of the proposed merger between Euronext and the New York Stock Exchange. Thierry Breton, the French finance minister, successfully pushed for a formally equal governance structure, but he repeatedly insisted that, while customers and employees would be consulted, the ultimate decision on the merger lay with shareholders (Entreprise et marché, July 5, 2006).

Demand for and opposition to government intervention

A look at the demand for government intervention in the NYSE/Euronext merger shows French business elites highly mobilized and deeply divided on the issue -possibly because the ownership composition of the stock exchange could affect a larger part of the corporate community than that of companies in the industrial sector. While the main beneficiaries of intervention against a foreign takeover of industrial companies (management and employees of the companies concerned) usually have higher stakes than their opponents (free-market ideologues and minority shareholders), the NYSE/ Euronext merger pitched Euronext management against Euronext users (that is, French issuers and financial intermediaries), all of whom had material interests at stake. 2006). Their policy preferences resembled those of the Socialist Party, which called on the government to "immediately take … responsible action by opposing the merger in such a way that economic patriotism, be it French or European, does not remain a mere slogan" (AFP, December 20, 2006). Interestingly, perhaps for the reasons identified below, the Socialists refrained from repeating this line of attack in the run-up to the presidential elections.

The following section explains why opponents of the transatlantic merger failed to build up political pressure for intervention, despite a political climate that -in the run-up to the 2007 presidential elections -was highly receptive to appeals to economic patriotism.

The discursive limitations of "economic patriotism"

Several discursive hurdles prevented successful instrumentalization of the economic patriotism discourse by opponents of the merger. First, patriotic sentiments among the electorate were difficult to mobilize for a company as foreign and removed from people's lives as Euronext. Unlike consumer products such as yoghurt and cars, financial services do not lend themselves well to the kind of emotional attachment prone to stirring patriotic sentiments, especially since they can be construed as elements of "Anglo-American style capitalism," even when the providers are French. In addition, the number of French jobs at stake was small. In 2006, the Paris branch of Euronext -the largest within the company -employed fewer than 400 people, mostly in positions that failed to spark feelings of solidarity in the average French worker. Moreover, direct and indirect shareholdings are still relatively scarce in France, where an extended public welfare state provides retirement pensions through taxation, contributions, and intergenerational redistribution, rather than through individual capitalization and private savings [START_REF] Montagne | Les fonds de pension entre protection sociale et spéculation financière[END_REF]).

Second, a convincing "patriotic" alternative to the transatlantic merger was not available. In other recent cases of government intervention, blockage of a cross-border merger typically resulted either in the French company remaining independent, or in a Franco-French alliance. 7 In the case of Euronext, failure to merge with NYSE was widely The resonance of appeals to economic patriotism at the European level suffered not only from the weakness of a European identity in general, but from distrust of "imperialist" Germany in particular. This allowed opponents of intervention to neutralize such appeals by presenting the choice between NYSE and Deutsche Börse as a choice between the frying pan and the fire. According to Daniel Bouton, chairman and CEO of Société Générale, one of the two investment banks advising NYSE with Citigroup on the operation, Frankfurt was trying to "strip Paris of its status as the main financial center on the continent, after having already obtained the seat of the Third, and perhaps most interestingly, questionable "patriotic credentials" contributed to weakening the influence of the business leaders calling for intervention. Understanding the credibility problems afflicting financial intermediaries requires the following background knowledge about the demutualization process of the Paris Stock Exchange. Historically, most stock exchanges, including the Paris Bourse, were owned and controlled by their first users, the stockbrokers. They were governed through a mutual structure, with member-owners contributing their time to governance and self-regulation. Profits were returned to member-owners in the form of lower access fees or other benefits (Chaddad 2003: 13). In recent years, many exchanges have changed their legal form and governance structure by separating ownership rights from membership rights -a process commonly referred to as demutualization. As a first step toward demutualization, most exchanges converted membership rights into common stock holdings, thus making members the legal owners of the corporation. After that, many exchanges went on to list their own securities on the stock market, thereby extending the possibility of ownership to outside investors [START_REF] Lee | The Governance of Financial Market Infrastructure[END_REF] ) had worked at the Belgian Finance Ministry until the mid-1990s, where he had contributed to the drafting and implementation of laws reforming the national financial sector.

Apart from the discursive hurdles spelled out above, opponents of the merger faced the additional difficulty that intervention conflicted with the neo-liberal paradigm which had guided financial sector policy-making in France and Europe since the 1980s. The decision not to intervene in the NYSE/Euronext merger coherently followed from earlier measures designed to enhance the international competitiveness of the French financial center. First steps toward stock market demutualization were taken as early as 1984 with reforms authorizing commercial banks to branch out into investment banking [START_REF] Lordon | Les quadratures de la politique économique[END_REF][START_REF] Feiertag | Greffe économétrique et genèse de l'école de la Banque de France[END_REF]. In March 1988, universal banks, insurance companies, and international brokerage houses were allowed to take control of the Paris Stock Exchange. The Compagnie nationale des agents de change, a hybrid organization controlled by a powerful guild of state-authorized officers under the direct supervision of the French Ministry of Finance, was dismantled and replaced by the corporation of French exchanges (Société des Bourses Françaises -SBF). 10 In June 1999, the SBF absorbed the three other French 10 To be accurate, the Compagnie des agents de change was replaced by three distinct entities: the Société des bourses françaises, the Stock Exchanges Council (Conseil des bourses de valeurs -CBV, now dissolved into the French Financial Markets Authority), and the French Association of Stockbrokerage Firms (Association française des sociétés de bourse -AFSB, now AMAFI). The Stock Exchanges Council was a peer-elected body, supervised by a government representative, which enacted and enforced the rules. The French Association of Stockbrokerage Firms repre-market operators: the Société du Nouveau Marché, dedicated to smaller companies, the MATIF and the MONEP for futures and options. In September 2000, the exchanges of Paris, Amsterdam, and Brussels merged to form Euronext [START_REF] Djelic | From Playground of the French Bourgeoisie to Global Operator: Reinventing the Paris Stock Exchange[END_REF]. When Euronext went public in 2001, French policy-makers did not insist on a hard core (noyau dur) of French shareholders for the Paris branch of Euronext, even though Euronext management, unlike the historical shareholders, had recommended measures to ensure ownership stability.

The French drive for financial sector competitiveness through liberalization was also in line with policies promoted by the European Commission. The latter aimed at the marginalization of direct state intervention in the ownership structure, governance, or strategy of firms; integration of the European financial sector through competition; and coordination of conflicting interests through marketization [START_REF] Mügge | Reordering the Marketplace: Competition Politics in European Finance[END_REF][START_REF] Posner | The Origins of Europe's New Stock Markets[END_REF][START_REF] Jabko | Playing the Market: A Political Strategy for Uniting Europe, 1985-2005[END_REF]. Underlying these policies was the conviction that financial market integration was more likely to result from enhanced competition between stock exchanges than from enhanced cooperation among fiercely competing stock exchanges. As [START_REF] Jabko | Playing the Market: A Political Strategy for Uniting Europe, 1985-2005[END_REF], [START_REF] Posner | The Origins of Europe's New Stock Markets[END_REF], and Denord and Schwartz (2010) demonstrate at length, this conviction stemmed partly from the prior failure of efforts to link the main European financial markets by encouraging cooperation, and partly from a long-lasting ideological stance.

Moreover, party-strategic calculations meant that political leaders had strong incentives to prevent the NYSE/Euronext merger from turning into a central campaign issue in the upcoming presidential elections. The presidential candidate for the conservative party, Nicolas Sarkozy, sought to differentiate himself from the incumbent President, Jacques Chirac, and his archrival Prime Minister Dominique de Villepin by promising a "rupture" with the past. His aim was to appear as a fresh figure despite coming from the ruling party and having served as Chirac's minister for five years. To achieve this, Sarkozy deliberately distanced himself -at least during the campaign -from Gaullist diplomatic and economic policies by embracing more neo-liberal, free-market positions and by displaying admiration for the United States and the Bush administration. Meanwhile, the Socialists also lacked incentives to exploit the NYSE/Euronext merger as a campaign issue. Their party had lost the 2002 election by failing to gain the expected support from working class voters [START_REF] Lefebvre | Le peuple vu par les socialistes[END_REF]. A campaign focus on the stock exchange was not deemed a promising remedy. Moreover, in the wake of the failed 2005 referendum on the European constitution, divisions within the Socialist party over the desirability of further European integration ran deep, and the promotion of Euronext as a European champion was feared to further alienate left-wing voters.

sented the employers' interests. For the purpose of this paper, it suffices to focus on the entity that operates the Paris Stock Exchange, that is to say, the Société des bourses françaises, which became Euronext Paris after the creation of the pan-European group in 2000.

Conclusion

In sum, our article maps the public discourse surrounding the NYSE/Euronext merger to help explain why opponents of the transatlantic merger failed in their appeals to "economic patriotism." Discursive strategies designed to justify discrimination against territorially defined outsiders ran into several hurdles, including weak patriotic sentiments for the company concerned; a lack of patriotic alternatives to the proposed merger; and the questionable patriotic credentials of those demanding intervention.

Whether lower discursive hurdles would have allowed the build-up of sufficient political pressure to provoke stronger government intervention is impossible to ascertain. The French state is more than a mere arena for pluralist struggles among competing interests; rather, the decision not to prevent the NYSE/Euronext merger was consistent with a long-standing policy agenda of financial liberalization, and there is no counterfactual evidence. Whether French policy-makers opted to reduce their involvement in the stock exchange business because they genuinely believed in the regulatory efficiency of market forces once installed -a view widespread among EU technocrats, especially within the Internal Market Directorate [START_REF] Posner | The Origins of Europe's New Stock Markets[END_REF]) -or because they failed to fully anticipate the consequences, is equally hard to establish. While most of them might have been fooled by the time-lag between the gradual sale of shares and the evident loss of French control over the exchange, some others (including the Finance Minister Thierry Breton, previously the CEO of Thomson and France Telecom, as well as the corporate lawyer Christine Lagarde, who was secretary of foreign trade at the time of the merger) acted out of conviction. Alain Madelin, a neo-liberal former French Finance Minister, for example, found it "rather obvious that a stock market enterprise be quoted on the stock market" (Business FM, Good Morning News, November 21, 2006).

Nevertheless, given the political context, it is plausible that the lack of broad electoral mobilization afforded policy-makers greater freedom to pursue their preferred agenda than they would otherwise have had. Even in statist France, elected politicians are never completely autonomous, and the timing of the merger -in the aftermath of the failed 2005 referendum on the EU constitution and in the run-up to the 2007 presidential elections -provided strong incentives for bowing to populist demands. The discursive hurdles identified above help explain why opponents of the merger failed to rally the public behind their calls for intervention.

Our article advances recent research on economic patriotism by identifying variables that help explain when governments choose to discriminate in favor of territorially defined insiders. To complement previous work on government action, we focus on the demand side -including the discursive dimension -of territorially based political intervention. By doing so, we also draw attention to hitherto unexplored effects of territorial ambiguities on the viability of economic patriotism. Demutualized stock exchanges have an ambiguous status as listed for-profit companies, on the one hand, and as trading platforms, on the other. As such, they can be portrayed either as national champions that are to be promoted wherever they choose to play, or as an essential part of the playing field that must be kept at home (or, by those opposing both kinds of political intervention, as ordinary private businesses that are best left alone). Where they are multinational enterprises, further ambiguities arise as to whether the national or the European level is the appropriate territorial reference for appeals to economic patriotism. Our article shows that, in the case of Euronext, such territorial ambiguities represented a discursive hurdle for the proponents of intervention.

To the literature on business-government relations, we contribute the insight that state withdrawal from the economy can lead to mismatched expectations regarding the allocation of responsibility for economic governance. Prominent members of the French business community expected to "have their cake and eat it." They used the new opportunities of demutualization to profitably sell control over the stock exchange to foreign investors without realizing that privatization also implied that the state could no longer be counted on to pick up the reins. Conversely, some politicians expressed disappointment that French shareholders of the newly demutualised stock exchange had chosen to pursue short-term material interests at the expense of the long-term public good. Both expectations are clearly incongruent with the idea of privatization, and one may doubt whether they were genuinely held. However, even if the mismatch of expectations was discursively construed on both sides in an effort to shift the blame, it shows that the allocation of responsibility for economic governance remains subject to frequent renegotiation, even after the formal withdrawal of the state. From a neo-Weberian perspective, one could analyze this situation in terms of an attempted re-patrimonialization of the state by the emancipated members of the "state nobility" (Bourdieu 1989). Business elites organized the dismantling of French state capitalism, but still count on their connections and credentials to influence the government whenever public action is required to serve their now-private interests (Dudouet/Grémont 2010; Jabko/Massoc 2011).

To research on the political implications of corporate ownership structure, we contribute new hypotheses regarding the relationship between "corporate insider" status and access to political privileges. Callaghan (2009aCallaghan ( , 2009b) ) and Schnyder (2011) favor of territorially defined insiders where the beneficiaries of discrimination are also "corporate insiders," capable of offering a quid pro quo for political favors.

Beyond that, our article opens up several avenues for future research. First, case studies of the political discourse surrounding other cross-border mergers in France and elsewhere would allow for a comparative assessment of the relationship between rhetoric, mobilization, and political action across sectors and countries. Across sectors, the takeover of the partly French-owned steel giant Arcelor by its Indian-owned rival Mittal in 2006 would make for an especially interesting comparison, because it shares not just the timing but also the multinational structure of the target company with the NYSE/ Euronext merger. Across countries, comparison with the failed 2006/2007 bid by Nasdaq for the London Stock Exchange would help determine whether financial sector companies, and stock exchanges in particular, inspire stronger "patriotic sentiments" in Anglo-Saxon economies than they do in France. Comparison with Deutsche Börse, which remains locally rooted in Frankfurt after failed efforts to expand abroad, would contribute to a better understanding of the interplay between the regional, national, and European levels of public actions taken to amend the industrial outcomes of market competition.

Second, our article raises questions regarding the causes of stock market demutualization that are worth pursuing in light of recent research on institutional change and, more specifically, capitalist development. We show that some historical owners of the Paris stock exchange expressed discontent with the loss of control that resulted from demutualization. Why, then, did they agree to sell their shares in the first place? Careful process-tracing would help assess whether the demutualization process was driven mainly by short-sightedness, whether it resulted from power struggles within an increasingly heterogeneous group of financial intermediaries, or whether it was imposed from above. This, in turn, would throw light on the mechanisms that ensure why gradual change in contemporary capitalism, including change in stock market governance, is "not random but patterned, proceeding toward liberalization rather than in no particular or in some other direction" (Streeck 2009: 230).

Third, future research should monitor the long-term consequences of stock market demutualization for economic governance. Our article describes how the progressive dismantling of the club mode of governing the Paris stock exchange affected the balance of power between the proponents and opponents of stock market patriotism. In the long-run, the shift from user-orientation to shareholder-value orientation is likely to further exacerbate tensions between users, owners, managers and regulators. The experience of Deutsche Börse, whose management board was forced to resign in 2005 after an acrimonious battle with activist investors, provides a flavor of things to come.

Despite a likely increase in political tensions, especially after the recent financial crisis, the phantom of "economic patriotism" that has long haunted the French financial center -including the Palais Brongniart -seems unlikely to reappear any time soon. While the famously strong ties between political and economic elites that underpinned postwar French dirigisme persist, the significance of state intervention has profoundly changed since the 1980s. Our case study shows that, by the mid-2000s, elite networks notwithstanding, the French government's commitment to financial deregulation had become strong enough to withstand calls for discrimination in favor of territorially defined insiders. Whether the triumph of neo-liberal market mechanisms over network-based coordination is cause for concern or for celebration is a normative question relevant to much of contemporary industrial policy.

2 The surprising absence of territorially based discrimination

  We thank Daniel Seikel, Cornelia Woll, and participants of the workshop on "Economic Patriotism" convened by Ben Clift and Cornelia Woll for their helpful comments. Julia Franke provided valuable research assistance. The project was funded by a DAAD-Procope grant. can increase the political pressure behind selfishly motivated demands by mobilizing broad support, and broad mobilization requires a successful appeal to some widely shared "public interest." Appeals to patriotic sentiments are frequently employed, presumably because such sentiments are widespread and easily tapped without need for complex technical argumentation. By revealing the limitations of this discursive strategy, our case study thus contributes to explaining when governments choose to pursue the kind of action classified by Clift and Woll.Beyond that, our article informs research on business-government relations and on the politics of corporate ownership. To the literature on business-government relations, we contribute the insight that state withdrawal from the economy can lead to mismatched expectations regarding the allocation of responsibility for economic governance. To research on political consequences of changes in the structure of corporate ownership, we contribute new hypotheses regarding the relationship between "corporate insider" status and access to political privileges.

	The term "economic patriotism," coined by French Prime Minister Dominique de Ville-
	pin in 2005, 2 has recently entered the political science vocabulary as a potential prism
	2	Villepin first promoted the term at a press conference on July 27, 2005, when he endorsed a parlia-

1 "NYSE Euronext opens 'NYSE Euronext London.' A new securities market targeting issuers seeking a London listing," press release, July 15, 2010. action Our empirical evidence derives from newspapers, interviews, and participant observation on the Paris premises of Euronext. Eighty volumes of newspaper articles compiled by Euronext Paris between 2000 and 2007 served as our main source of press coverage. Twelve interviews held between 2006 and 2010 with prominent figures of the Paris financial centre or insider informants (see "Interviews" in "Sources" at the end of the paper) provided background information. Beyond that, one of the authors had the opportunity to witness the in-house dynamics of Euronext at first hand, through his position as an assistant to the Euronext director of international affairs in Paris from October 2001 until August 2002, and as an assistant to the Euronext director of European affairs in Brussels from August to November 2003.

The article proceeds as follows. Section 2 highlights gaps in existing research on economic patriotism and explains how our case selection contributes to filling them. Section 3 maps the preferences and discursive strategies of key French stakeholders concerning political intervention in the NYSE/Euronext merger. We conclude with suggestions for further research. mentary report written by the conservative MP Bernard Carayon, Patriotisme économique, de la guerre à la paix économique

(Paris, Le Rocher, 2005)

, in reaction to a possible raid by PepsiCo on Danone (available at: http://www.archives.premier-ministre.gouv.fr/villepin/acteurs/interven-tions_premier_ministre_9/conferences_presse_526/conference_presse_mensuelle_53667.html).

  managers of Euronext wanted the merger to go through. Accordingly, they repeatedly insisted that theirs was a private company. As early as 2001, Euronext CEO Jean-François Theodore presented demutualized stock exchanges as "an industry like any other" and warned against "speak[ing] of alliances as if we are diplomats"(Business Week, June 11, 2001). The same view was promoted by influential French economists, including members of the prime minister's Council of Economic Advisors (Conseil d'analyse économique). Some of the most vocal economists in the debate, including Bertrand Jacquillat (professor at Sciences Po Paris, chairman and CEO of the financial consultancy Associés en Finance) and Christian Saint-Etienne (professor at the University of Tours, lobbyist at Schell et Associés), were simultaneously members of the Cercle des économistes, a prominent French think tank subsidized by Euronext. is not in the best interest of the European market place" (The Wall Street Journal Europe, October 6, 2006).Apart from lobbying behind the scenes, some of the business leaders opposing the merger openly demanded state intervention. Gérard de La Martinière (FFSA and MEDEF) wanted the French government to "bang its fist on the table"(Reuters, November 9, 2006). Axel Miller, CEO of the Franco-Belgian bank Dexia, complained after the merger that "the finance ministers should have taken care of this matter … The stock exchange is a vital instrument for growth and employment, and for the market economy at large. The failure to preserve it reveals the current political void" (Les Echos, December 18,

5

Question posed to Jean-Pierre Jouyet during a talk at Institut Droit Dauphine in Paris, October 21, 2009. Top 6 By contrast, many issuers and financial intermediaries, including former owners of the Stock Exchange, opposed the transatlantic merger (Bloomberg News, October 11, 2006). Gérard de La Martinière, head of FFSA, the powerful French federation of insurance companies and spokesman for MEDEF, the French peak business federation, pleaded for "European connections that would allow us to enlarge the capital pool while remaining in our own zone of monetary activity" (Reuters, November 9, 2006). The European Association of Listed Companies, chaired by Alain Joly, CEO of the French blue chip Air Liquide, complained that "[t]he proposed governance structure that puts NYSE in control, gives no assurance in the long run as to the preservation of the interests of European issuers" (Bloomberg News, October 11, 2006). Claude Bébéar, supervisory board president of AXA and a leading figure of French capitalism, objected to demutualized stock exchanges per se and wanted them to be kept under the control of their users, at least through a shareholding pact. Michel Pébereau, supervisory board president of BNP and arguably the most powerful banker in France (Jabko/Massoc 2011), worried that a transatlantic move would dilute the influence of his bank more severely than consolidation at the continental European level would. A high-profile study of NYSE's and Deutsche Börse's takeover offers, commissioned by Paris Europlace, a public-private association charged with promoting the Paris financial center, and conducted by Henri Lachmann, CEO of Schneider Electric, concluded that "the transatlantic acquisition

  to result in a merger with Deutsche Börse. Proponents of intervention tried to overcome this discursive hurdle by appealing to "economic patriotism" at the European level: Arthuis argued that, "one year after the failure of the referendum on the[Lisbon] treaty … this new project of allowing the pan-European stock exchange Euronext to fall under the control of the New York Stock Exchange is a woeful sign and a confession of European abandonment"(Boursorama, July 7, 2006). Ernest-Antoine Seillière, then president of the European employer federation UNICE (now called BUSINESS-EUROPE) warned that, "[i]f the Americans become masters of our financial market, then this is a severe defeat for our European project" (Valeurs actuelles, June 9, 2006). Lachmann found it "essential that we continue to build Europe, and the Europe of stock markets should take priority over the acquisition of Euronext by the NYSE"(Figaro, October 6, 2006). French MP Jacques Myard (UMP), known for his vocal support for industrial policy at the national and EU levels, saw the NYSE/Euronext merger as "further proof of the vassalization of Europe by the United States." 8

7

For example, in 1999, the French government opposed a merger between Elf and Italy's dominant oil company, Ente Nazionale Idrocarburi (ENI), and discouraged Elf from looking for a foreign partner which could act as a "white knight" to stave off a hostile bid from its French rival Total. In 2003, it scared Switzerland's Novartis out of bidding for Aventis and instead arranged for Aventis to merge with the French company Sanofi-Synthélabo (see

Callaghan 2009b)

.

expected

  German alliance drew ammunition from an off-hand comment by Kurt Viermetz, head of Deutsche Börse's supervisory board, who had boasted, in March 2006, that one could "turn off the lights in the rest of Europe" if Euronext were to move to Frankfurt (Futures Magazine, September 1, 2006). Tensions associated with previous French-German attempts to create European champions -including Sanofi-Aventis, Siemens/Alstom and earlier disappointments which turned into bitter competition between the Paris Stock Exchange and the Deutsche Börse, provided further grounds for skepticism.

European Central Bank six years earlier"

(Le Point, January 17, 2007)

. Theodore had made the same point more subtly, by justifying his rejection of Deutsche Börse's merger offer on the grounds that "[t]heir vision of Europe was focused on Frankfurt … whereas we are a 21st century company. We are represented in all our capital cities"

(Bloomberg, July 6, 2006)

. In the same vein, Oliver Lefebvre, board member of Euronext and president of the Brussels Stock Exchange, insisted that "[t]he proposal by Deutsche Börse runs counter to the interests of the Eurozone … By favoring such a merger, one would destroy the only cross-border example that works at present"

(L'Echo, June 27, 2006)

. Opponents of a Franco-8 AFP, December 19, 2006. This line of argument was the one promoted by Image 7, the influential French lobbying consultancy hired by Deutsche Börse to promote its interests in France

(Raulot 2007: 152-157

).

  ; see Callaghan/Lagneau-Ymonet 2010). The French stock exchange, by then part of Euronext, went public in July 2001. At a time when strategic management was all about disinvestment in peripheral activities and financial consolidation in the wake of the dot-com bust, French financial intermediaries gradually sold their stakes in Euronext. They made good money 9 in return for ceding control of the exchange to international institutional investors, such as Fidelity, and activist hedge funds, including Harris Associates, Atticus, and TCI.Calls for state intervention in the name of economic patriotism by those who had sold their own means of protecting French interests sparked widespread resentment. Philippe Marini, rapporteur of the Finance Commission in the French Senate and a close ally of Jean-François Theodore, advised the historical shareholders to "stop complaining about a situation which they themselves ha[d] brought about"(La Tribune, November 13, 2006). He observed that "[if] large French and European banks had kept their shares instead of walking away with their capital gains a little prematurely, Euronext could very well have pursued its development autonomously and continued to integrate further European exchanges into its federal structure" (Bloomberg TV: Forum, July 4, 2006). Jean Arthuis, president of the Finance Commission in the French Senate and a strong opponent of the NYSE/Euronext merger, "deplore[d] the fact that Euronext, which was formed in 2000, thought it a good idea to go public in 2001" and scolded the banks for having betraying the public interest by realizing their capital gains. In his view, this was particularly unacceptable because "[i]f anyone should have an understanding of the general interest, it is the banks. After all, when they are confronted with difficulties that pose a risk for the financial system, it is the state which comes to their rescue" (Bour-9French intermediaries obtained seven Euronext shares, valued at 24 euros each, for every share of the Société des bourses françaises (SBF), the previous operator of the Paris Stock Exchange. The deal was highly attractive because SBF shares were poorly valued, at historical cost, in the books of the financial intermediaries, and because market conditions were generally poor in the wake of the dot-com bust and September 11, 2001. sorama, July 7, 2006). Henri Lachmann, author of the above-mentioned position paper by Paris Europlace, pointed out that "[t]he French banks sold their shares and recently had the chance to regain control by acquiring a large block of shares that had been placed on the market … Anyone who does not seize such an opportunity should not go around giving lessons on citizenship to others" (Le Figaro, November 21, 2006). By contrast, French Euronext managers backing the merger enjoyed strong credibility because of their success in founding Euronext -which had transformed the quasi-public French, Belgian, and Dutch exchanges into a highly profitable privatized multinational capable of rivaling the London and Frankfurt stock exchanges. The federally structured Euronext convinced many that cross-border stock market alliances could help Paris in its competition against London and Frankfurt -not least because its French CEO, Jean-François Theodore, was celebrated as a clever strategist in the international business press. In June 2002, the influential magazine Institutional Investors even gave him the front page with an explicit tribute, "Théodore [sic] Rex". Theodore's credibility with French Treasury officials was further aided by close network connections to top-tier civil servants. After graduating from the elite École nationale d'administration, Theodore had worked at the French Treasury from 1974 to 1989 before becoming chairman and CEO of the Société des bourses françaises and, from 2000, the head of Euronext. Likewise, his Belgian counterpart Olivier Lefebvre, president of the Brussels Stock Exchange (PhD in economics from the Université Catholique de Louvain, MBA from Cornell University

  compare the effects of concentrated ownership on the politics of corporate governance across countries and over time. Their findings suggest that the relevance of network-based corporate governance mechanisms, which declines with ownership dispersion, affects preferences regarding legislative measures or merger proposals that threaten to disrupt network-based coordination. 11 In the case of the Paris stock exchange, increased ownership dispersion coincided with a declining willingness of policy-makers to discriminate in favor of territorial insiders. This may suggest that politicians are more inclined to discriminate in

11 Where dispersed ownership prevails, as it does in the UK, "insider" networks are less significant than are "outsider," "arms-length" mechanisms of corporate governance, which might explain weaker political resistance to foreign takeovers, minority shareholder protection, and active markets for corporate control.

According to[START_REF] Coval | Home Bias at Home: Local Equity Preference in Domestic Portfolios[END_REF] home bias is observable even within countries.

In January 2007, Professor Jacques Hamon from the University Paris-Dauphine, Bertrand Jacquillat, and Christian Saint-Etienne released a report on Global Stock Exchange Consolidation, which portrayed stock exchange consolidation as inevitable and supported the tie-up between Euronext and NYSE.

Recent Titles in the Publication Series of the MPIfG

MPIfG Discussion Papers DP 10/13 L. Gruss., G. Piotti Blurring the Lines: Strategic Deception and Self-Deception in Markets DP 10/12 W. Streeck E Pluribus Unum? Varieties and Commonalities of Capitalism DP 10/11 M. R. Busemeyer, M. A. Cattaneo, S. C. Wolter Individual Policy Preferences for Vocational versus Academic Education: Micro Level Evidence for the Case of Switzerland DP 10/10 S. Freye Germany's New Top Managers? The Corporate Elite in Flux, 1960-2005 DP 10/9 J. J. Fernandez Economic Crises, High Public Pension Spending and Blameavoidance Strategies: Pension Policy Retrenchments in 14 Social-insurance Countries, 1981-2005 DP 10/8 M. Höpner, A. Schäfer Polanyi in Brussels? Embeddedness and the Three Dimensions of European Economic Integration MPIfG Working Papers WP 10/8 R. Mayntz Die transnationale Ordnung globalisierter Finanzmärkte: Was lehrt uns die Krise? WP 10/7 J. Beckert Are We Still Modern? Inheritance Law and the Broken Promise of the Enlightenment WP 10/6 S. Neckel Refeudalisierung der Ökonomie: Zum Strukturwandel kapitalistischer Wirtschaft WP 10/5 R. Mayntz Legitimacy and Compliance in Transnational Governance WP 10/4 S. Kirchner Organizational Identities and Institutions: Dynamics of the Organizational Core as a Question of Path Dependence WP 10/3 W. Streeck, D. Mertens An Index of Fiscal Democracy WP 10/2 M. Höpner Warum betreibt der Europäische Gerichtshof Rechtsfortbildung? Die Politisierungshypothese

Sources

Interviews

The authors conducted one-to two-hour interviews with the following persons in their homes or offices in 2009 and 2010. The interviewees agreed that notes could be taken and that their names be mentioned, but declined to be recorded. Jean-Louis Beffa, CEO, Saint-Gobain (March 2009) Pervenche Berès, President, Committee of the European Parliament for Economic and Monetary Affairs (March 2010) Arnaud de Bresson, General delegate, Paris Europlace (May 2010) Bertrand Collomb, CEO, Lafarge (June 2010) Jacques Hamon, Professor, University Paris-Dauphine (May 2010) Pierre de Lauzun, Deputy general director, Fédération des Banques Françaises (May 2010) Helmut Mader, Managing Director, Mader Capital Resources GmbH (November 2009) Philippe Marini, Rapporteur, Finance Commission of the French Senate (September 2010) Gérard Pfauwadel, President, Unigestion (February 2009) Michel Prada, President, Autorité des Marchés Financiers (October 2009) Edouard de Lencquesaing, Special advisor, Paris Europlace (February 2009) Jean-François Theodore, CEO, Euronext (March and September 2010) George Ugeux, CEO, Galileo Partners (April 2010)

Ordering Information

MPIfG Discussion Papers Order printed copies from the MPIfG (you will be billed) or download PDF files from the MPIfG website (free).

MPIfG Working Papers

Order printed copies from the MPIfG (you will be billed) or download PDF files from the MPIfG website (free).

MPIfG Books

At bookstores; abstracts on the MPIfG website. www.mpifg.de Go to Publications.

New Titles

Consult our website for the most complete and upto-date information about MPIfG publications and publications by MPIfG researchers. To sign up for newsletters and mailings, please go to Service on the MPIfG website. Upon request to info@mpifg.de, we will be happy to send you our Recent Publications brochure.

ERPA


Changbo Chen
email: changbo.chen@hotmail.com

Svyatoslav Covanov
email: svyatoslav.covanov@gmail.com

Farnam Mansouri
email: mansouri.farnam@gmail.com

Marc Moreno Maza

Ning Xie

Yuzhen Xie
email: yuzhenxie@yahoo.ca

Parallel Integer Polynomial Multiplication

Keywords: Polynomial algebra, symbolic computation, parallel processing, cache complexity, multi-core architectures

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

I. INTRODUCTION

Polynomial multiplication and matrix multiplication are at the core of many algorithms in symbolic computation. Expressing, in terms of multiplication time, the algebraic complexity of an operation, like univariate polynomial division, or the computation of a characteristic polynomial is a standard practice, see for instance the landmark book [START_REF] Zur Gathen | Modern Computer Algebra[END_REF]. At the software level, the motto "reducing everything to multiplication" is also common, see for instance the computer algebra systems AXIOM [START_REF] Jenks | Axiom, the scientific computation system[END_REF] Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF], NTL [START_REF] Shoup | NTL: A library for doing number theory[END_REF] and FLINT [START_REF] Hart | FLINT: Fast Library for Number Theory[END_REF].

With the advent of hardware accelerator technologies, such as multicore processors and Graphics Processing Units (GPUs), this reduction to multiplication is of course still desirable, but becomes more complex, since both algebraic complexity and parallelism need to be considered when selecting and implementing a multiplication algorithm. In fact, other performance factors, such as cache usage or CPU pipeline optimization, should be taken into account on modern computers, even on single-core processors. These observations guide the developers of projects like SPI-RAL [START_REF] Püschel | SPIRAL: Code generation for DSP transforms[END_REF] or FFTW [START_REF] Frigo | The design and implementation of FFTW3[END_REF].

This paper is dedicated to the multiplication of dense univariate polynomials with integer coefficients targeting multicore processors. We note that the parallelization of sparse (both univariate and multivariate) polynomial multiplication on those architectures has already been studied by Gastineau & Laskar in [START_REF] Gastineau | Highly scalable multiplication for distributed sparse multivariate polynomials on many-core systems[END_REF], and by Monagan & Pearce in [START_REF] Monagan | Parallel sparse polynomial multiplication using heaps[END_REF]. From now on, and throughout this paper, we focus on dense polynomials. The case of modular coefficients was handled in [START_REF] Moreno Maza | FFT-based dense polynomial arithmetic on multi-cores[END_REF], [START_REF]Balanced dense polynomial multiplication on multicores[END_REF] by techniques based on multidimensional FFTs. Considering now integer coefficients, one can reduce to the univariate situation through Kronecker's substitution, see the implementation techniques proposed by Harvey in [START_REF] Harvey | Faster polynomial multiplication via multipoint Kronecker substitution[END_REF].

A first natural parallel solution for multiplying univariate integer polynomials is to consider divide-and-conquer algorithms where arithmetic counts are saved thanks to distributivity of multiplication over addition. Well-known instances of this solution are the multiplication algorithms of Toom & Cook, among which Karatsuba's method is a special case. As we shall see with the experimental results of Section IV, this is a practical solution. However, the parallelism is limited by the number of ways in the recursion. Moreover, augmenting the number of ways increases data conversion costs and makes implementation quite complicated, see the work by Bodrato and Zanoni for the case of integer multiplication [START_REF] Bodrato | Integer and polynomial multiplication: towards optimal Toom-Cook matrices[END_REF]. As in their work, our implementation includes the 4-way and 8-way cases. In addition, the algebraic complexity of an N -way Toom-Cook algorithm is not in the desirable complexity class of algorithms based on FFT techniques.

Turning our attention to this latter class, we first considered combining Kronecker's substitution (so as to reduce multiplication in Z[x] to multiplication in Z) and the algorithm of Schönhage & Strassen [START_REF] Schönhage | Schnelle multiplikation großer zahlen[END_REF]. The GMP library [START_REF] Granlund | GNU MP 6.0 Multiple Precision Arithmetic Library[END_REF] provides indeed a highly optimized implementation of this latter algorithm [START_REF] Gaudry | A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm[END_REF]. Despite of our efforts, we could not obtain much parallelism from the Kronecker substitution part of this approach. It became clear at this point that, in order to go beyond the performance (in terms of arithmetic count and parallelism) of our parallel 8-way Toom-Cook code, our multiplication code had to rely on a parallel implementation of FFTs.

Based on the work of our colleagues from the SPIRAL and FFTW projects, and based on our experience on the subject of FFTs [START_REF] Moreno Maza | FFT-based dense polynomial arithmetic on multi-cores[END_REF], [START_REF]Balanced dense polynomial multiplication on multicores[END_REF], [START_REF] Meng | Spiral-generated modular FFT algorithms[END_REF], we know that an efficient way to parallelize FFTs on multicore architectures is the socalled row-column algorithms, see http://en.wikipedia.org/wiki/ Fast Fourier transform, which implies to view 1-D FFTs as multi-dimensional FFTs and thus differs from the approach of Schönhage & Strassen.

Reducing polynomial multiplication in Z[y] to multidimensional FFTs over a finite field, say Z/pZ, implies transforming integers to polynomials over Z/pZ.

Chmielowiec in [START_REF] Chmielowiec | Parallel algorithm for multiplying integer polynomials and integers[END_REF] experimented a similar method combined with the Chinese Remaindering Algorithm (CRA). As we shall see, using a big prime approach instead of a small primes approach opens the door for using "faster FFTs" and reducing algebraic complexity w.r.t to a CRA-based scheme.

As a result of all these considerations, we obtained the algorithm that we propose in this paper. We stress the fact that our purpose was not to design an algorithm asymptotically optimal by some complexity measure. Our purpose is to provide a parallel solution for dense integer polynomial multiplication on multicore architectures. In terms of algebraic complexity, our algorithm is asymptotically faster than that of Schönhage & Strassen [START_REF] Schönhage | Schnelle multiplikation großer zahlen[END_REF] while being asymptotically slower than that of Fürer [START_REF] Fürer | Faster integer multiplication[END_REF]. Our code is part of the Basic Polynomial Algebra Subprograms and is publicly available at http://www.bpaslib.org/.

Let a(y), b(y) ∈ Z[y] and a positive integer d such that d -1 is the maximum degree of a and b, that is, d = max(deg(a), deg(b)) + 1. We aim at computing the product c(y) := a(y) b(y). We propose an algorithm whose principle is sketched below. A precise statement of this algorithm is given in Section II, while complexity results and experimental results appear in Sections III and IV. 2) Let m > 4H be an integer, where H is the maximum absolute value of the coefficients of the integer polynomial C(x, y) := A(x, y)B(x, y). The positive integers m, K and the polynomials A(x, y), B(x, y) are built such that the polynomials C + (x, y) := A(x, y)B(x, y) mod x K + 1 and C -(x, y) := A(x, y)B(x, y) mod x K -1 are computed over Z/mZ via FFT techniques, while the following equation holds over Z:

C(x, y) = C + (x, y) 2 (x K -1) + C -(x, y) 2 (x K + 1).
(1) 3) Finally, one recovers the product c(y) by evaluating the above equation at x = β. Of course, the polynomials A(x, y), B(x, y) are also constructed such that their total bit size is proportional to that of a(y), b(y), respectively. In our software experimentation, this proportionality factor ranges between 2 and 4. Moreover, the number β is a power of 2 such that evaluating the polynomials C + (x, y) and C -(x, y) (whose coefficients are assumed to be in binary representation) at x = β amounts only to addition and shift operations.

Further, for our software implementation on 64-bit computer architectures, the number m can be chosen to be either one machine word size prime p or a product p 1 p 2 of two such primes, or a product p 1 p 2 p 3 of three such primes. Therefore, in practice, the main arithmetic cost of the whole procedure is that of two, four or six convolutions, those latter being required for computing C + (x, y) and C -(x, y). All the other arithmetic operations (for constructing A(x, y), B(x, y) or evaluating the polynomials C + (x, y) and C -(x, y)) are performed in single or double fixed precision at a cost which is proportional to that of reading/writing the byte vectors representing A(x, y), B(x, y), C + (x, y) and C -(x, y).

Theorem 1 below gives estimates for the work, the span and the cache complexity of the above algorithm. Recall that our goal is not to obtain an algorithm which is asymptotically optimal for one of these complexity measures. Instead, our algorithm is designed to be practically faster, on multicore architectures, than the other algorithms that are usually implemented for the same purpose of multiplying dense (univariate) polynomials with integer coefficients. A detailed proof of this result is elaborated in Section III. The assumptions K ∈ Θ(d) and M ∈ Θ(log d) are not strong. It is, indeed, possible to reduce to this situation by means of the balancing techniques presented in [START_REF]Balanced dense polynomial multiplication on multicores[END_REF]. Applying those techniques would only increase the work by a constant multiplicative factor, typically between 2 and 4.

It follows from this result that our proposed algorithm is asymptotically faster than combining Kronecker's substitution and Schönhage & Strassen. Indeed, with the notations of Theorem 1, this latter approach runs in O(dN log(dN ) log log(dN )) machine word operations.

While it is possible to obtain a poly-log time for the span this would correspond to an algorithm with high parallelism overheads. Hence, we prefer to state a bound corresponding to our implementation. By using multi-dimensional FFTs, we obtain a parallel algorithm which is practically efficient, as illustrated by the experimental results of Section IV. In particular, the algorithm scales well. In contrast, parallelizing a k-way Toom Cook algorithms (by executing concurrently the point-wise multiplication, see [START_REF] Mansouri | On the parallelization of integer polynomial multiplication[END_REF] yields only a ratio work to span in the order of k, that is, a very limited scalability. Finally, our cache complexity estimate is sharp. Indeed, we control finely all intermediate steps with this respect, see Section III.

To illustrate the benefits of a parallelized dense univariate polynomial multiplication, we integrated our code into the univariate real root isolation code presented in [START_REF] Chen | Cache complexity and multicore implementation for univariate real root isolation[END_REF] together with a parallel version of Algorithm (E) from [START_REF] Zur Gathen | Fast algorithms for Taylor shifts and certain difference equations[END_REF] for Taylor shifts. The results reported in [START_REF] Chen | The basic polynomial algebra subprograms[END_REF] show that this integration has substantially improved the performance of our real root isolation code.

II. MULTIPLYING INTEGER POLYNOMIALS VIA TWO

CONVOLUTIONS

We write a(y)

= d-1 i=0 a i y i , b(y) = d-1 i=0 b i y i and c(y) = 2d-2 i=0 c i y i , where a i , b i , c i are integers and c(y) = a(y)b(y). Let N be a non-negative integer such that each coefficient α of a or b satisfies -2 N -1 ≤ α ≤ 2 N -1 -1 (2)
Therefore, using two's complement, every such coefficient α can be encoded with N bits. In addition, the integer N is chosen such that N writes

N = KM with K = N and M = N, (3)
for K, M ∈ N.

It is helpful to think of M as a small number in comparison to K and d, say M is less than the bit-size, called w, of a machine word. For the theoretical analysis of our algorithm, we shall assume that K and M are functions of d satisfying K ∈ Θ(d) and M ∈ Ω(log d). We denote by DetermineBase(a, b, w) a function call returning (N, K, M ) satisfying the constraints of (3).

Let (N, K, M ) := DetermineBase(a, b, w) and define β = 2 M . We write

a i = K-1 j=0 a i,j β j , and b i = K-1 j=0 b i,j β j , (4)
where each a i,j and b i,j are signed integers in the closed range

[-2 M -1 , 2 M -1 -1]. Then, we define A(x, y) = d-1 i=0 ( K-1 j=0 a i,j x j )y i , B(x, y) = d-1 i=0 ( K-1 j=0 b i,j x j )y i , (5) and
C(x, y) = A(x, y)B(x, y) with

C(x, y) = 2d-2 i=0 2K-2 j=0 c i,j x j y i , (6)
where c i,j ∈ Z. By BivariateRepresentation(a, N, K, M ), we denote a function call returning A(x, y) as defined above.

Observe that the polynomial c(y) is clearly recoverable from C(x, y) by evaluating this latter polynomial at x = β.

The following sequence of equalities will be useful:

C = A B = d-1 i=0 ( K-1 j=0 ai,jx j )y i d-1 i=0 ( K-1 j=0 bi,jx j )y i = 2d-2 i=0 +m=i K-1 k=0 a ,k x k K-1 h=0 b m,h x h y i = 2d-2 i=0 +m=i 2K-2 j=0 k+h=j a ,k b m,h x j y i = 2d-2 i=0 2K-2 j=0 ci,jx j y i = 2K-2 j=0 2d-2 i=0 ci,jy i x j = K-1 j=0 2d-2 i=0 ci,jy i x j + x K K-2 j=0 2d-2 i=0 ci,j+K y i x j , (7)
where we have

c i,j = +m=i k+h=j a ,k b m,h , 0 ≤ i ≤ 2d-2, 0 ≤ j ≤ 2K-2.
(8) Since the modular products A(x, y)B(x, y) mod x K + 1 and A(x, y)B(x, y) mod x K -1 are of interest, we define the bivariate polynomial over Z

C + (x, y) := 2d-2 i=0 c + i (x) y i where c + i (x) := K-1 j=0 c + i,j x j (9)
with c + i,j := c i,j -c i,j+K , and the bivariate polynomial over Z

C -(x, y) := 2d-2 i=0 c - i (x) y i where c - i (x) := K-1 j=0 c - i,j x j
(10) with c - i,j := c i,j + c i,j+K . Thanks to Equation [START_REF] Frigo | The design and implementation of FFTW3[END_REF], we observe that we have

C + (x, y) ≡ A(x, y)B(x, y) mod x K + 1 , C -(x, y) ≡ A(x, y)B(x, y) mod x K -1 . (11)
Since the polynomials x K + 1 and x K -1 are coprime for all integer K ≥ 1, we deduce Equation (1). Since β is a power of 2, evaluating the polynomials C + (x, y), C -(x, y) and thus C(x, y) (whose coefficients are assumed to be in binary representation) at x = β amounts only to addition and shift operations. A precise algorithm is described in Section II-B. Before that, we turn our attention to computing C + (x, y) and C -(x, y) via FFT techniques.

A. Computing C + (x, y) and C -(x, y) via FFT From Equation [START_REF]Balanced dense polynomial multiplication on multicores[END_REF], it is natural to consider using FFT techniques for computing both C + (x, y) and C -(x, y). Thus, in order to compute over a finite ring supporting FFT, we estimate the size of the coefficients of C + (x, y) and C -(x, y). Recall that for 0 ≤ i ≤ 2d -2, we have

c + i,j = c i,j -c i,j+K = +m=i k+h=j a ,k b m,h - +m=i k+h=j+K a ,k b m,h . (12)
Since each a ,k and each b m,h has bit-size at most M , the absolute value of each coefficient c + i,j is bounded over by 2 d K 2 2M . The same holds for the coefficients c - i,j . Since the coefficients c + i,j and c - i,j may be negative, we consider a prime number p such that we have

p > 4 d K 2 2M . ( 13
)
From now on, depending on the context, we freely view the coefficients c + i,j and c - i,j either as elements of Z or as elements of Z/p. Indeed, the integer p is large enough for this identification and we use the integer interval [-p-1 2 , p-1 2 ] to represent the elements of Z/p.

The fact that we follow a big prime approach instead of an approach using machine word size primes and the Chinese Remaindering Algorithm will be justified in Section III.

A second requirement for the prime number p is that the field Z/p should admit appropriate primitive roots of unity for computing the polynomials C + (x, y) and C -(x, y) via cyclic convolution and negacylic convolution as in Relation [START_REF]Balanced dense polynomial multiplication on multicores[END_REF], that is, both 2d-1 and K must divide p-1. In view of utilizing 2-way FFTs, if p writes 2 k q + 1 for an odd integer q, we must have:

(2d -1) ≤ 2 k and K ≤ 2 k . (14)
It is well-known that there are approximately

h 2 k-1 log (h)
prime numbers p of the form 2 k q + 1 for a positive integer q and such that p < h holds, see [START_REF] Zur Gathen | Modern Computer Algebra[END_REF]. Hence the number of prime numbers of the form 2 k q + 1 less than 2 and greater than or equal to 2 -1 is approximately 2 -1 2 k-1 . For this latter fraction to be at least one, we must have

2 -log 2 ( )+1 ≥ 2 k .
With [START_REF] Schönhage | Schnelle multiplikation großer zahlen[END_REF] this yields: 2 -log 2 ( )+1 ≥ (2d -1) and 2 -log 2 ( )+1 ≥ K, from where we derive the sufficient condition:

-log 2 ( ) ≥ max(log 2 (d), log 2 (K)). (15)
We denote by RecoveryPrime(d, K, M ) a function call returning a prime number p satisfying Relation ( 13) and [START_REF] Granlund | GNU MP 6.0 Multiple Precision Arithmetic Library[END_REF]. We shall see in Section III that under two realistic assumptions, namely M ∈ Ω(d) and K ∈ Θ(d), Relation (13) implies Relation [START_REF] Granlund | GNU MP 6.0 Multiple Precision Arithmetic Library[END_REF]. Finally, we denote by e the smallest number of w-bit words necessary to write p. Hence we have

e ≥ 2 + log 2 (d K) + 2M w . (16)
Let θ be a 2K-th primitive root of unity in Z/p. We define ω = θ 2 , thus ω is a K-th primitive root in Z/p. For univariate polynomials u(x), v(x) ∈ Z[x] of degree at most K -1, computing u(x) v(x) mod x K -1, p via FFT is a well-known operation, see Algorithm 8.16 in [START_REF] Zur Gathen | Modern Computer Algebra[END_REF]. Using the row-column algorithm for two-dimensional FFT, one can compute C -(x, y) ≡ A(x, y)B(x, y) mod x K -1, p , see [START_REF]Balanced dense polynomial multiplication on multicores[END_REF], [START_REF] Moreno Maza | FFT-based dense polynomial arithmetic on multi-cores[END_REF] for details. We denote by CyclicConvolution(A, B, K, p) the result of this calculation.

We turn our attention to the negacylic convolution, namely A(x, y)B(x, y) mod x K + 1, p . We observe that C + (x, y) ≡ A(x, y)B(x, y) mod x K + 1, p holds if only if C + (θx, y) ≡ A(θx, y)B(θx, y) mod x K -1, p does. Thus, defining C (x, y) := C + (θx, y), A (x, y) := A(θx, y) and B (x, y) := B(θx, y) we are led to compute A (x, y)B (x, y) mod x K -1, p , which can be done as CyclicConvolution(A , B , K, p). Then, the polynomial

C + (x, y) mod x K -1, p is recovered from C (x, y) mod x K -1, p as C + (x, y) ≡ C (θ -1 x, y) mod x K -1, p , (17)
and we denote by NegacyclicConvolution(A, B, K, p) the result of this process. We dedicate a section to the final step of our algorithm, that is, the recovery of the product c(y) from the polynomials C + (x, y) and C -(x, y).

B. Recovering c(y) from C + (x, y) and C -(x, y)

We naturally assume that all numerical coefficients are stored in binary representation. Thus, recovering c(y) as C(β, y) from Equation (1) involves only addition and shift operations. Indeed, β is a power of 2. Hence, the algebraic complexity of this recovery is essentially proportional to the sum of the bit sizes of C + (x, y) and C -(x, y). Therefore, the arithmetic count for computing these latter polynomials (by means of cyclic and negacyclic convolutions) dominates that of recovering c(y). Nevertheless, when implemented on a modern computer hardware, this recovery step may contribute in a significant way to the total running time. The reasons are that: (1) both the convolution computations and recovery steps incur similar amounts of cache misses, and (2) the memory traffic implied by those cache misses are a significant portion of the total running time.

We denote by RecoveringProduct(C + (x, y), C -(x, y), β) a function call recovering c(y) from C + (x, y), C -(x, y) and β = 2 M . We start by stating below a simple procedure for this operation:

1) u(y) := C + (β, y), 2) v(y) := C -(β, y), 3) c(y) := u(y)+v(y) 2 + -u(y)+v(y) 2 2 N .
To further describe this operation and, later on, in order to discuss its cache complexity and parallelization, we specify the data layout. From Relation (16), we can assume that each coefficient of the bivariate polynomials C + (x, y), C -(x, y) can be encoded within e machine words. Thus, we assume that C + (x, y) (resp. C -(x, y)) is represented by an array of (2d -1) K e machine words such that, for 0 ≤ i ≤ 2d -2 and 0 ≤ j ≤ K -1, the coefficient c + i,j (resp. c - i,j ) is written between the positions (K i + j)e and (K i + j)e + e -1, inclusively. Thus, this array can be regarded as the encoding of a 2-D matrix whose i-th row is c + i (x) (resp. c - i (x)). Now, we write

u(y) := 2d-2 i=0 u i y i and v(y) := 2d-2 i=0 v i y i ; (18)
thus, from the definition of u(y), v(y), for 0 ≤ i ≤ 2d -2, we have

u i = K-1 j=0 c + i,j 2 M j and v i = K-1 j=0 c - i,j 2 M j . (19)
Denoting by H + , H -the largest absolute value of a coefficient in C + (x, y), C -(x, y), we deduce

|u i | ≤ H + 2 M K -1 2 M -1 and |v i | ≤ H - 2 M K -1 2 M -1 . ( 20
)
From the discussion justifying Relation (13), we have

H + , H -≤ 2 d K 2 2M , (21)
and with [START_REF] Mansouri | On the parallelization of integer polynomial multiplication[END_REF] we derive

|u i |, |v i | ≤ 2 d K 2 M +N . (22)
Indeed, recall that N = K M holds. We return to the question of data layout. Since each of c + i,j or c - i,j is a signed integer fitting within e machine words, it follows from [START_REF] Mansouri | On the parallelization of integer polynomial multiplication[END_REF] that each of the coefficients u i , v i can be encoded within

f := N/w + e (23)
machine words. Hence, we store each of the polynomials u(y), v(y) in an array of (2d -1) × f machine words such that the coefficient in degree i is located between position f i and position f (i + 1) -1. Finally, we come to the computation of c(y). We have

c i = u i + v i 2 + 2 N v i -u i 2 , (24)
which implies

|c i | ≤ 2 d K 2 M +N (1 + 2 N ). (25)
Relation [START_REF] Schönhage | algorithms -a multitape Turing machine implementation[END_REF] implies that the polynomial c(y) can be stored within an array of (2d-1)×2f machine words. Of course, a better bound than (25) can be derived by simply expanding the product a(y) b(y), leading to

|c i | ≤ d 2 2N -2 . ( 26
)
The ratio between the two bounds given by ( 25) and ( 26) tells us that the extra amount of space required by our algorithm is O(log 2 (K) + M ) bits per coefficient of c(y).

In practice, we aim at choosing K, M such that M ∈ Θ(log 2 (K)), and if possible M ≤ w. Hence, this extra space amount can be regarded as small and thus satisfactory.

C. The algorithm in pseudo-code

With the procedures that were defined in this section, we are ready to state our algorithm for integer polynomial multiplication. A(x,y),B(x,y). Note that this data layout question was handled for C -(x, y), C + (x, y) and c(y) in Section II-B.

Input

In the sequel, we view a(y), b(y) as dense in the sense that each of their coefficients is assumed to be essentially of the same size. Hence, from the definition of N , see Relation (2), we assume that each of a(y), b(y) is stored within an array of d× N/w machine words such that the coefficient in degree i is located between positions N/w i and N/w (i+1)-1.

Finally, we assume that each of the bivariate integer polynomials A(x, y), B(x, y) is represented by an array of d × K machine words whose (K × i + j)-th coefficient is a i,j , b i,j respectively, for 0 ≤ i ≤ d -1 and 0 ≤ j ≤ K -1.

D. Parallelization

One of the initial motivations of our algorithm design is to take advantage of the parallel FFT-based routines for multiplying dense multivariate polynomials over finite fields that have been proposed in [START_REF] Moreno Maza | FFT-based dense polynomial arithmetic on multi-cores[END_REF], [START_REF]Balanced dense polynomial multiplication on multicores[END_REF]. To be precise, these routines provide us with a parallel implementation of the procedure CyclicConvolution, from which we easily derive a parallel implementation of NegacyclicConvolution.

Lines 1 and 4 can be ignored in the analysis of the algorithm. Indeed, one can simply implement DetermineBase and RecoveryPrimes by look-up in precomputed tables.

For parallelizing Lines 2 and 3, it is sufficient in practice to convert concurrently all the coefficients of a(y) and b(y) to univariate polynomials of Z[y]. Similarly, for parallelizing Line 7 it is sufficient again to compute concurrently the coefficients of u(y), v(y) and then those of c(y).

III. COMPLEXITY ANALYSIS

In this section, we analyze the algorithm stated in Section II-C. We estimate its work and span as defined in the fork-join concurrency model [START_REF] Blumofe | Space-efficient scheduling of multithreaded computations[END_REF]. The reader unfamiliar with this model can regard the work as the time complexity on a multitape Turing machine [START_REF] Schönhage | algorithms -a multitape Turing machine implementation[END_REF] and the span as the minimum parallel running time of a "fork-join program". Such programs use only two primitive language constructs, namely fork and join, in order to express concurrency. Since the fork-join model has no primitive constructs for defining parallel for-loops, each of those loops is simulated by a divide-and-conquer procedure for which non-terminal recursive calls are forked, see [START_REF] Leiserson | The Cilk++ concurrency platform[END_REF] for details. Hence, in the fork-join model, the bit-wise comparison of two vectors of size n has a span of O(log(n)) bit operations. This is actually the same time estimate as in the Exclusive-Read-Exclusive-Write PRAM [START_REF] Stockmeyer | Simulation of parallel random access machines by circuits[END_REF], [START_REF] Gibbons | A more practical PRAM model[END_REF] model, but for a different reason.

We shall also estimate the cache complexity [START_REF] Frigo | Cache-oblivious algorithms[END_REF] of the serial counterpart of our algorithm for an ideal cache of Z words and with L words per cache line.

The reader unfamiliar with this notion may understand it as a measure of memory traffic or, equivalently on multicore processors, as a measure of data communication. Moreover, the reader should note that the ratio work to cache complexity indicates how an algorithm is capable of re-using cached data. Hence, the larger is the ratio, the better.

We denote by W i , S i , Q i the work, span and cache complexity of Line i in the algorithm stated in Section II-C. As mentioned before, we can ignore the costs of Lines 1 and 4. Moreover, we can use W 2 , S 2 , Q 2 as estimates for W 3 , S 3 , Q 3 , respectively. Similarly, we can use the estimates of Line 5 for the costs of Line 6. Thus, we only analyze the costs of Lines 2, 5 and 7.

A. Choosing K, M and p

In order to analyze the costs associated with the cyclic and negcyclic convolutions, we shall specify how K, M , p are chosen. We shall assume thereafter that K and M are functions of d satisfying the following asymptotic relations:

K ∈ Θ(d) and M ∈ Θ(log d). (27)
It is a routine exercise to check that these assumptions together with Relation (13) imply Relation [START_REF] Granlund | GNU MP 6.0 Multiple Precision Arithmetic Library[END_REF]. Relations ( 27) and ( 16) imply that we can choose p and thus e such that we have e ∈ Θ(log d).

(

) 28
Here comes our most important assumption: one can choose p and thus e such that computing an FFT of a vector of size s over Z/p[x], amounts to

F arith (e, s) ∈ O s log(s) log(e) (29)
arithmetic operations in Z/p, whenever e ∈ Θ(log s) holds.

Since each arithmetic operation in Z/p can be done within O(e log(e) log log(e)) machine-word operations (using the multiplication algorithm of Schönhage and Strassen). Hence:

F word (e, s) ∈ O(s e log(s) log log(e)) (30)
machine-word operations, whenever e ∈ Θ(log s) holds.

Using the fork-join model, the corresponding span is O(log 2 (s) log 2 (e) log log(e)) machine-word operations. Relation ( 29) can be derived with other technical assumptions about Z/p from the use of the algorithm proposed in [START_REF] Harvey | Even faster integer multiplication[END_REF]. The analysis proposed in Section 2.6 of [START_REF] Covanov | Putting Fürer algorithm into practice[END_REF] proposes an analysis specific to this case. Later, Relation (29) was derived in [START_REF] Covanov | Fast integer multiplication using generalized Fermat primes[END_REF] assuming that p is a generalized Fermat prime. B. Analysis of BivariateRepresentation(a(y), N, K, M )

Converting each coefficient of a(y) to a univariate polynomial of Z[x] requires O(N ) bit operations; thus,

W 2 ∈ O(d N ) and S 2 ∈ O(log(d) N ). (31)
The latter log(d) factor comes from the fact that the parallel for-loop corresponding to "for each coefficient of a(y)" is executed as a recursive function with O(log(d)) nested recursive calls. Considering the cache complexity, and taking into account the data layout specified in Section II-C, one can observe that converting a(y) to A(x, y) leads to O( dN wL + 1) cache misses for reading a(y) and O( dKe L + 1) cache misses for writing A(x, y). Therefore, we have:

Q 2 ∈ O dN wL + dK log 2 (dK) wL + 1 . (32)
C. Analysis of CyclicConvolution(A, B, K, p)

Following the techniques developed in [START_REF] Moreno Maza | FFT-based dense polynomial arithmetic on multi-cores[END_REF], [START_REF]Balanced dense polynomial multiplication on multicores[END_REF], we compute A(x, y)B(x, y) mod x K -1, p by 2-D FFT of format K ×(2d-1). In the direction of y, we need to do K FFTs of size 2d -1 leading to O(K F word (e, 2d -1)) machine word operations. In the direction of x, we need to compute 2d -1 convolutions (i.e. products in Z[x]/ x K -1, p ) leading to O((2d -1) F word (e, K)) machine word operations. Using Relations ( 27), ( 28) and ( 30 ) machine word operations. Finally, from the results of [START_REF] Frigo | Cache-oblivious algorithms[END_REF], and assuming that Z is large enough to accommodate a few elements of Z/p, we have This second estimate holds also for the total number of cache misses for computing c(y) from u(y), v(y). Thus, we have Q 7 ∈ O( d (K e + N + e)/L + 1). We note that the quantity K e + N + e can be replaced in above asymptotic upper bounds by K(log 2 (d K) + 3 M ).

Q 6 ∈ O(1 + (deK/L)(1 + log Z (deK))). (36)

E. Proof of Theorem 1

Recall that analyzing our algorithm reduces to analyzing Lines 2, 5, 7. Based on the results obtained above for W 2 , W 5 , W 7 , with Relations (31), ( 35), (37), respectively, it follows that the estimate for the work of the whole algorithm is given by W 5 , leading to the result in Theorem 1. Meanwhile, the span of the whole algorithm is dominated by S 7 and one obtains the result in Theorem 1. Finally, the cache complexity estimate in Theorem 1 comes from adding up Q 2 , Q 5 , Q 7 and simplifying.

IV. EXPERIMENTATION

We realized an implementation of a modified version of the algorithm presented in Section II. The only modification is that we rely on prime numbers p that do not satisfy Equation [START_REF] Harvey | Even faster integer multiplication[END_REF]. In particular and unfortunately, our implementation is not using yet generalized Fermat primes. Overcoming this limitation is work in progress. Currently, our prime numbers are of machine word size. As a consequence, the work of the implemented algorithm is O(dKM log(dK)(log(dK) + 2M )), which is asymptotically larger than the work of the approach combining Kronecker's substitution and Schönhage & Strassen. This helps understanding why the speedup factor of our parallel implementation over the integer polynomial multiplication code of FLINT (which is a serial implementation of the algorithm of Schönhage & Strassen) is less than the number of cores that we use.

However, this latter complexity estimate yields a (modest) optimization trick: since the asymptotic upper bound O(dKM log(dK)(log(dK) + 2M )) increases slower with M than with d or K, it is advantageous to make M large. We do that by using two machine word primes (and the Chinese Remaindering Algorithm) instead of a single prime for computing two modular images of C + (x, y) and C -(x, y) that we combine by the Chinese Remaindering Algorithm.

Moreover, our parallel implementation outperforms the integer polynomial multiplication code of MAPLE 2015, which is also a parallel code.

Our code is written in the multi-threaded language CilkPlus [START_REF] Leiserson | The Cilk++ concurrency platform[END_REF] and compiled with the CilkPlus branch of GCC. Our experimental results were obtained on an 48core AMD Opteron 6168, running at 900MHz with 256 GB of RAM and 512KB of L2 cache. Table II gives running times for the five multiplication algorithms that we have implemented:

• KSs stands for Kronecker's substitution combined with Schönhage & Strassen algorithm [START_REF] Schönhage | Schnelle multiplikation großer zahlen[END_REF]; note this is a serial implementation, running on 1 core. • CVL 2 p is the prototype implementation of the modified version of the algorithm described in Section II, running on 48 cores. In this implementation, two machine-word size Fourier primes are used instead of a single big prime for computing C + (x, y) and C -(x, y).

• DnCp is a straightforward 4-way divide-and-conquer parallel implementation of plain multiplication, run on 48 cores, see Chapter 2 of [START_REF] Mansouri | On the parallelization of integer polynomial multiplication[END_REF].

• Toom 4

p is a parallel implementation of 4-way Toom-Cook, run on 48 cores, see Chapter 2 of [START_REF] Mansouri | On the parallelization of integer polynomial multiplication[END_REF].

• Toom 8 p is a parallel implementation of 8-way Toom-Cook, run on 48 cores, see Chapter 2 of [START_REF] Mansouri | On the parallelization of integer polynomial multiplication[END_REF]. In addition, Table II gives running times for integer polynomial multiplication performed with FILNT 2.4.3 [START_REF] Hart | FLINT: Fast Library for Number Theory[END_REF] and Maple 2015. In Table II, for each example, the degree d of the input polynomial is equal to the coefficient bit size N . The input polynomials a(y), b(y) are random and dense.

Figure 1 shows the running time comparison among our algorithm, FILNT 2.4.3 [START_REF] Hart | FLINT: Fast Library for Number Theory[END_REF] and Maple 2015. The input of each test case is a pair of polynomials of degree d where each coefficient has bit size N . Timings (in sec.) appear along the vertical axis. Two plots are provided: one for which d = N holds and one for d is much smaller than N .

From Table II and Figure 1, we observe that our implementation CVL 2 p performs better on sufficiently large input data, compared to its counterparts.

V. CONCLUDING REMARKS

We have presented a parallel FFT-based method for multiplying dense univariate polynomials with integer coefficients. Our approach relies on two convolutions (cyclic and negacyclic) of bivariate polynomials which allow us to take advantage of the row-column algorithm for 2D FFTs. The proposed algorithm is asymptotically faster than that of Schönhage & Strassen.

In our implementation, the data conversions between univariate polynomials over Z and bivariate polynomials over Z/pZ are highly optimized by means of low-level "bit hacks" thus avoiding software multiplication of large integers. In fact, our code relies only and directly on machine word operations (addition, shift and multiplication).

Our experimental results show this new algorithm has a high parallelism and scale better than its competitor algorithms.

Nevertheless, there is still room for improvement in the implementation. Using a single big prime (instead of two machine-word size primes and the Chinese Remaindering Algorithm) and requiring that it is a generalized Fermat prime would make the implemented algorithm follow strictly the algorithm presented in Section II. The source of the algorithms discussed in this chapter are freely available at the web site of Basic Polynomial Algebra Subprograms (BPAS-Library) 1 .

  , y), B(x, y) over Z (by converting the integer coefficients of a(y), b(y) to univariate polynomials of Z[x], where x is a new variable) such that a(y) = A(β, y) and b(y) = B(β, y) hold for some β ∈ Z (and, of course, such that we have deg(A, y) = deg(a) and deg(B, y) = deg(b)).

Theorem 1 :

 1 Let N be a positive integer such that every such coefficient of a or b can be written with at most N bits. Let K, M be two positive integers greater than 1 and such that N = KM . Assume that K and M are functions of d satisfying the following asymptotic relations K ∈ Θ(d) and M ∈ Θ(log d). Then, the above algorithm for multiplying a(y) and b(y) has a work of O(dKM log(dK) log log(log(d))) word operations, a span of O(log 2 (d)KM ) word operations and incurs O(1 + (dM K/L)(1 + log Z (dM K))) cache misses.

  : a(y), b(y) ∈ Z[y]. Output: the product a(y) b(y) 1: (N, K, M ) := DetermineBase(a(y), b(y), w) 2: A(x, y) := BivariateRepresentation(a(y), N, K, M ) 3: B(x, y) := BivariateRepresentation(b(y), N, K, M ) 4: p := RecoveryPrime(d, K, M ) 5: C -(x, y) := CyclicConvolution(A, B, K, p) 6: C + (x, y) := NegacyclicConvolution(A, B, K, p) 7: c(y) := RecoveringProduct(C + (x, y), C -(x, y), 2 M ) 8: return c(y)In order to analyze the complexity of our algorithm, it remains to specify the data layout for a(y), b(y),

W 5 ∈ 35 )S 5 ∈

 5355 ), the work of one 2-D FFT of format K × (2d -1) amounts to: O(KF word (e, 2d -1)) + O((2d -1)F word (e, K)) = O(Ke(2d -1)(log(2d -1) + log(K)) log log(e)) = O(Ke(2d -1) log((2d -1)K) log log(e)) = O(KM (2d -1) log((2d -1)K) log log(log(d))) (33) machine word operations, while the span amounts to: O((log(K) log 2 (d) + log(d) log 2 (K)) log 2 (e) log log(e)) = O(log(K) log(d) log(dK) log 2 (log(d)) log log(log(d))). O(dKM log(dK) log log(log(d))) and (O(log(K) log(d) log(dK) log 2 (log(d)) log log(log(d))

D.

  Analysis of RecoveringProduct(C + (x, y), C -(x, y), 2 M ) Converting each coefficient of u(y) and v(y) from the corresponding coefficients C + (x, y) and C -(x, y) requires O(K e) bit operations. Then, computing each coefficient of c(y) requires O(N + e w) bit operations. Thus we have W 7 ∈ O(d (K e+N +e)) and S 7 ∈ O(log(d) (K e+N +e)) (37) word operations. Converting C + (x, y), C -(x, y) to u(y), v(y) leads to O( d K e/L + 1) cache misses for reading C + (x, y), C -(x, y) and O( d(N/w + e)/L + 1) cache misses for writing u(y), v(y).

Figure 1 .

 1 Figure 1. Dense integer polynomial multiplication: CVL 2 p (BPAS) vs FLINT vs Maple 2015.

  Table I lists generalized Fermat primes of practical interest. See [31] for more details.

	p	max{2 k s.t. 2 k | p -1}
	(2 63 + 2 53 ) 2 + 1	2 106
	(2 64 -2 50 ) 4 + 1	2 200
	(2 63 + 2 34 ) 8 + 1	2 272
	(2 62 + 2 36 ) 16 + 1	2 576
	(2 62 + 2 56 ) 32 + 1	2 1792
	(2 63 -2 40 ) 64 + 1	2 2500
	(2 64 -2 28 ) 128 + 1	2 3584
		Table I
	GENERALIZED FERMAT PRIMES OF PRACTICAL INTEREST.

Table II TIMINGS

 II OF POLYNOMIAL MULTIPLICATION WITH d = N .

	d, N	CVL 2 p	DnCp	Toom 4 p	Toom 8 p	KSs	FLINTs	Maple 18 s
	2 10	0.139	0.11	0.046	0.059	0.057	0.016	0.06
	2 11	0.196	0.17	0.17	0.17	0.25	0.067	0.201
	2 12	0.295	0.58	0.67	0.64	1.37	0.42	0.86
	2 13	0.699	2.20	2.79	2.73	5.40	1.671	3.775
	2 14	1.927	8.26	10.29	8.74	20.95	7.178	17.496
	2 15	9.138	30.75	35.79	33.40	92.03	32.112	84.913
	2 16	33.04	122.1	129.4	115.9	*Err.	154.69	445.67

http://bpaslib.org/

ACKNOWLEDGMENTS

The authors would like to thank IBM Canada Ltd and NSERC of Canada for supporting their work.