Properties and algorithms of the (n, k)-star graphs

The (n, k)-star interconnection network was proposed in 1995 as an attractive alternative to the n-star topology in parallel computation. The (n, k )-star has significant advantages over the n-star which itself was proposed as an attractive alternative to the popular hypercube. The major advantage of the (n, k )-star network is its scalability, which makes it more flexible than the n-star as an interconnection network. In this thesis, we will focus on finding graph theoretical properties of the (n, k )-star as well as developing parallel algorithms that run on this network. The basic topological properties of the (n, k )-star are first studied. These are useful since they can be used to develop efficient algorithms on this network. We then study the (n, k )-star network from algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms for basic communication, prefix computation, and sorting, etc. A literature review of the state-of-the-art in relation to the (n, k )-star network as well as some open problems in this area are also provided.

Properties and algorithms of the (n, k)-arrangement graphs

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Planar Topological Defects in Unconventional Superconductors

In this work, we consider the properties of planar topological defects in unconventional superconductors. Specifically, we calculate microscopically the interaction energy of domain walls separating degenerate ground states in a chiral p-wave fermionic superfluid. The interaction is mediated by the quasiparticles experiencing Andreev scattering at the domain walls. As a by-product, we derive a useful general expression for the free energy of an arbitrary nonuniform texture of the order parameter in terms of the quasiparticle scattering matrix. The thesis is structured as follows. We begin with a historical review of the theories of superconductivity (Sec. 1.1), which led the way to the celebrated Bardeen-Cooper- Schrieffer (BCS) theory (Sec. 1.3). Then we proceed to the treatment of superconductors with so-called "unconventional pairing" in Sec. 1.4, and in Sec. 1.5 we introduce the specific case of chiral p-wave superconductivity. After introducing in Sec. 2 the domain wall (DW) model that will be considered throughout the work, we derive the Bogoliubov-de Gennes (BdG) equations in Sec. 3.1, which determine the quasiparticle excitation spectrum for a nonuniform superconductor. In this work, we use the semiclassical (Andreev) approximation, and solve the Andreev equations (which are a particular case of the BdG equations) in Sec. 4 to determine the quasiparticle spectrum for both the single- and two-DW textures. The Andreev equations are derived in Sec. 3.2, and the formal properties of the Andreev scattering coefficients are discussed in the following subsection. In Sec. 5, we use the transfer matrix method to relate the interaction energy of the DWs to the scattering matrix of the Bogoliubov quasiparticles. This facilitates the derivation of an analytical expression for the interaction energy between the two DWs in Sec. 5.3. Finally, to illustrate the general applicability our method, we apply it in Sec. 6 to the interaction between phase solitons in a two-band s-wave superconductor.