Please read the abstract in the dissertation / Dissertation (MSc)--University of Pretoria, 2009. / Physics / unrestricted

This dissertation explores Random Neural Networks (RNNs) in several aspects and their applications. First, Novel RNNs have been proposed for dimensionality reduction and visualization. Based on Extreme Learning Machines (ELMs) and Self-Organizing Maps (SOMs) a new method is created to identify the important variables and visualize the data. This technique reduces the curse of dimensionality and improves furthermore the interpretability of the visualization and is tested on real nursing survey datasets. ELM-SOM+ is an autoencoder created to preserves the intrinsic quality of SOM and also brings continuity to the projection using two ELMs. This new methodology shows considerable improvement over SOM on real datasets. Second, as a Supervised Learning method, ELMs has been applied to the hierarchical multiscale method to bridge the the molecular dynamics to continua. The method is tested on simulation data and proven to be efficient for passing the information from one scale to another. Lastly, the regularization of ELMs has been studied and a new regularization algorithm for ELMs is created using a modified Lanczos Algorithm. The Lanczos ELM on average divide computational time by 20 and reduce the Normalized MSE by 14% comparing with regular ELMs.

Accurate numerical solution of time-dependent, high-dimensional partial differential equations (PDEs) usually requires efficient numerical techniques and massive-scale parallel computing. In this thesis, we implement and evaluate discretization schemes suited for PDEs of higher dimensionality, focusing on high order of accuracy and low computational cost. Spatial discretization is particularly challenging in higher dimensions. The memory requirements for uniform grids quickly grow out of reach even on large-scale parallel computers. We utilize high-order discretization schemes and implement adaptive mesh refinement on structured hyperrectangular domains in order to reduce the required number of grid points and computational work. We allow for anisotropic (non-uniform) refinement by recursive bisection and show how to construct, manage and load balance such grids efficiently. In our numerical examples, we use finite difference schemes to discretize the PDEs. In the adaptive case we show how a stable discretization can be constructed using SBP-SAT operators. However, our adaptive mesh framework is general and other methods of discretization are viable. For integration in time, we implement exponential integrators based on the Lanczos/Arnoldi iterative schemes for eigenvalue approximations. Using adaptive time stepping and a truncated Magnus expansion, we attain high levels of accuracy in the solution at low computational cost. We further investigate alternative implementations of the Lanczos algorithm with reduced communication costs. As an example application problem, we have considered the time-dependent Schrödinger equation (TDSE). We present solvers and results for the solution of the TDSE on equidistant as well as adaptively refined Cartesian grids. / eSSENCE

In this thesis three methods LMGS, TQR and GR are applied to solve an inverseeigenvalue problem. We list the numerical results and compare the accuracy of the computed Jacobi matrix $T$ and the associated orthogonal matrix $Q$, wherethe columns of $Q^T$ are the eigenvectors of $T$. In the application of this inverse eigenvalue problem, the Fourier coefficients of $h(x)=e^x$ relative to the orthonormal polynomials associatedwith $T$ are evaluated, and these values are used to compute the least squarescoefficients of $h$ relative to the Chebyshev polynomials. We list thesenumerical results and compare them as our conclusion.

We present in this thesis a series of studies on the physical properties of some one dimensional systems. In particular we study the low energy properties of various spin chains and a junction of Luttinger wires. For spin chains we specifically look at the role of perturbations like frustrating interactions and dimerisation in a nearest neighbour chain and the formation of magnetisation plateaus in two kinds of models; one purely theoretical and the other motivated by experiments. In our second subject of interest we study using a renormalisation group analysis the effect of spin dependent scattering at a junction of Luttinger wires. We look at the physical effects caused by the interplay of electronic interactions in the wires and the scattering processes at the junction. The thesis begins with an introductory chapter which gives a brief glimpse of the ideas and techniques used in the specific problems that we have worked on. Our work on these problems is then described in detail in chapters 25. We now present a brief summary of each of those chapters. In the second chapter we look at the ground state phase diagram of the mixed-spin sawtooth chain, i.e a system where the spins along the baseline are allowed to be different from the spins on the vertices. The spins S1 along the baseline interact with a coupling strength J1(> 0). The coupling of the spins on the vertex (S2) to the baseline spins has a strength J2. We study the phase diagram as a function of J2/J1 [1]. The model exhibits a rich variety of phases which we study using spinwave theory, exact diagonalisation and a semi-numerical perturbation theory leading to an effective Hamiltonian. The spinwave theory predicts a transition from a spiral state to a ferrimagnetic state at J2S2/2J1S1 = 1 as J2/J1 is increased. The spectrum has two branches one of which is gapless and dispersionless (at the linear order) in the spiral phase. This arises because of the infinite degeneracy of classical ground states in that phase. Numerically, we study the system using exact diagonalisation of up to 12 unit cells and S1 = 1 and S2 =1/2. We look at the variation of ground state energy, gap to the lowest excitations, and the relevant spin correlation functions in the model. This unearths a richer phase diagram than the spinwave calculation. Apart from revealing a possibility of the presence of more than one kind of spiral phases, numerical results tell us about a very interesting phase for small J2. The spin correlation function (for the spin1/2s) in this region have a property that the nextnearest-neighbour correlations are much larger than the nearest neighbour correlations. We call this phase the NNNAFM (nextnearest neighbour antiferromagnet) phase and provide an understanding of this phase by deriving an effective Hamiltonian between the spin1/2s. We also show the existence of macroscopic magnetisation jumps in the model when one looks at the system close to saturation fields. The third chapter is concerned with the formation of magnetisation plateaus in two different spin models. We show how in one model the plateaus arise because of the competition between two coupling constants, and in the other because of purely geometrical effects. In the first problem we propose [2] a class of spin Hamiltonians which include as special cases several known systems. The class of models is defined on a bipartite lattice in arbitrary dimensions and for any spin. The simplest manifestation of such models in one dimension corresponds to a ladder system with diagonal couplings (which are of the same strength as the leg couplings). The physical properties of the model are determined by the combined effects of the competition between the ”rung” coupling (J’ )and the ”leg/diagonal” coupling (J ) and the magnetic field. We show that our model can be solved exactly in a substantial region of the parameter space (J’ > 2J ) and we demonstrate the existence of magnetisation plateaus in the solvable regime. Also, by making reasonable assumptions about the spectrum in the region where we cannot solve the model exactly, we prove the existence of first order phase transitions on a plateau where the sublattice magnetisations change abruptly. We numerically investigate the ladder system mentioned above (for spin1) to confirm all our analytical predictions and present a phase diagram in the J’/J - B plane, quite a few of whose features we expect to be generically valid for all higher spins. In the second problem concerning plateaus (also discussed in chapter 3) we study the properties of a compound synthesised experimentally [3]. The essential feature of the structure of this compound which gives rise to its physical properties is the presence of two kinds of spin1/2 objects alternating with each other on a helix. One kind has an axis of anisotropy at an inclination to the helical axis (which essentially makes it an Ising spin) whereas the other is an isotropic spin1/2 object. These two spin1/2 objects interact with each other but not with their own kind. Experimentally, it was observed that in a magnetic field this material exhibits magnetisation plateaus one of which is at 1/3rd of the saturation magnetisation value. These plateaus appear when the field is along the direction of the helical axis but disappear when the field is perpendicular to that axis. The model being used for the material prior to our work could not explain the existence of these plateaus. In our work we propose a simple modification in the model Hamiltonian which is able to qualitatively explain the presence of the plateaus. We show that the existence of the plateaus can be explained using a periodic variation of the angles of inclination of the easy axes of the anisotropic spins. The experimental temperature and the fields are much lower than the magnetic coupling strength. Because of this quite a lot of the properties of the system can be studied analytically using transfer matrix methods for an effective theory involving only the anisotropic spins. Apart from the plateaus we study using this modified model other physical quantities like the specific heat, susceptibility and the entropy. We demonstrate the existence of finite entropy per spin at low temperatures for some values of the magnetic field. In chapter 4 we investigate the longstanding problem of locating the gapless points of a dimerised spin chain as the strength of dimerisation is varied. It is known that generalising Haldane’s field theoretic analysis to dimerised spin chains correctly predicts the number of the gapless points but not the exact locations (which have determined numerically for a few low values of spins). We investigate the problem of locating those points using a dimerised spin chain Hamiltonian with a ”twisted” boundary condition [4]. For a periodic chain, this ”twist” consists simply of a local rotation about the zaxis which renders the xx and yy terms on one bond negative. Such a boundary condition has been used earlier for numerical work whereby one can find the gapless points by studying the crossing points of ground states of finite chains (with the above twist) in different parity sectors (parity sectors are defined by the reflection symmetry about the twisted bond). We study the twisted Hamiltonian using two analytical methods. The modified boundary condition reduces the degeneracy of classical ground states of the chain and we get only two N´eel states as classical ground states. We use this property to identify the gapless points as points where the tunneling amplitude between these two ground states goes to zero. While one of our calculations just reproduces the results of previous field theoretic treatments, our second analytical treatment gives a direct expression for the gapless points as roots of a polynomial equation in the dimerisation parameter. This approach is found to be more accurate. We compare the two methods with the numerical method mentioned above and present results for various spin values. In the final chapter we present a study of the physics of a junction of Luttinger wires (quantum wires) with both scalar and spin scattering at the junction ([5],[6]). Earlier studies have investigated special cases of this system. The systems studied were two wire junctions with either a fully transmitting scattering matrix or one corresponding to disconnected wires. We extend the study to a junction of N wires with an arbitrary scattering matrix and a spin impurity at the junction. We study the RG flows of the Kondo coupling of the impurity spin to the electrons treating the electronic interactions and the Kondo coupling perturbatively. We analyse the various fixed points for the specific case of three wires. We find a general tendency to flow towards strong coupling when all the matrix elements of the Kondo coupling are positive at small length scales. We analyse one of the strong coupling fixed points, namely that of the maximally transmitting scattering matrix, using a 1/J perturbation theory and we find at large length scales a fixed point of disconnected wires with a vanishing Kondo coupling. In this way we obtain a picture of the RG at both short and long length scales. Also, we analyse all the fixed points using lattice models to gain an understanding of the RG flows in terms of specific couplings on the lattice. Finally, we use to bosonisation to study one particular case of scattering (the disconnected wires) in the presence of strong interactions and find that sufficiently strong interactions can stabilise a multichannel fixed point which is unstable in the weak interaction limit.

Large sparse matrices arise in many applications, especially in the major problems of Cryptography of factoring integers and computing discrete logarithms. We focus attention on such matrices called sieve matrices generated after the sieving stage of the algorithms for integer factoring. We need to solve large sparse system of equations Bx = 0, with sieve matrices B arising in this context. The traditional Gaussian elimination, with a cubic run time, is not efficient for handling such matrices. Better algorithms for such input matrices are the quadratic runtime algorithms based on Block Lanczos(BL) or Wiedemann techniques. Of these two, BL is even better for large integer factoring algorithms. We carry out an efficient implementation of the Block Lanczos algorithm for finding the vectors in the null space of the the sieve matrix. We report our test results using our implementation for matrices of sizes up to 106. We plan to use this implementation in our ongoing projects on factoring the large RSA challenge integers of sizes 640 bits(called RSA-640) and beyond. So it is useful to exploit possible parallelism. We propose a scheme for parallelizing certain steps of the Block Lanczos method, taking advantage of structural properties of the sieve matrix. The sizes of matrices arising in integer factoring context are quite large. Hence we also discuss some techniques that are used to reduce the size of the sieve matrix. We also consider the last stage of the NFS Algorithm for finding square roots of large algebraic numbers and outline a sketch of our algorithm.

La solution numérique des systèmes dynamiques est un moyen efficace pour étudier des phénomènes physiques complexes. Cependant, dans un cadre à grande échelle, la dimension du système rend les calculs infaisables en raison des limites de mémoire et de temps, ainsi que le mauvais conditionnement. La solution de ce problème est la réduction de modèles. Cette thèse porte sur les méthodes de projection pour construire efficacement des modèles d'ordre inférieur à partir des systèmes linéaires dynamiques de grande taille. En particulier, nous nous intéressons à la projection sur la réunion de plusieurs sous-espaces de Krylov standard qui conduit à une classe de modèles d'ordre réduit. Cette méthode est connue par l'interpolation rationnelle. En se basant sur ce cadre théorique qui relie la projection de Krylov à l'interpolation rationnelle, quatre algorithmes de type Lanczos rationnel pour la réduction de modèles sont proposés. Dans un premier temps, nous avons introduit une méthode adaptative de type Lanczos rationnel par block pour réduire l'ordre des systèmes linéaires dynamiques de grande taille, cette méthode est basée sur l'algorithme de Lanczos rationnel par block et une méthode adaptative pour choisir les points d'interpolation. Une généralisation de ce premier algorithme est également donnée, où différentes multiplicités sont considérées pour chaque point d'interpolation. Ensuite, nous avons proposé une autre extension de la méthode du sous-espace de Krylov standard pour les systèmes à plusieurs-entrées plusieurs-sorties, qui est le sous-espace de Krylov global. Nous avons obtenu des équations qui décrivent cette procédure. Finalement, nous avons proposé une méthode de Lanczos étendu par block et nous avons établi de nouvelles propriétés algébriques pour cet algorithme. L'efficacité et la précision de tous les algorithmes proposés, appliqués sur des problèmes de réduction de modèles, sont testées dans plusieurs exemples numériques. / Numerical solution of dynamical systems have been a successful means for studying complex physical phenomena. However, in large-scale setting, the system dimension makes the computations infeasible due to memory and time limitations, and ill-conditioning. The remedy of this problem is model reductions. This dissertations focuses on projection methods to efficiently construct reduced order models for large linear dynamical systems. Especially, we are interesting by projection onto unions of Krylov subspaces which lead to a class of reduced order models known as rational interpolation. Based on this theoretical framework that relate Krylov projection to rational interpolation, four rational Lanczos-type algorithms for model reduction are proposed. At first, an adaptative rational block Lanczos-type method for reducing the order of large scale dynamical systems is introduced, based on a rational block Lanczos algorithm and an adaptive approach for choosing the interpolation points. A generalization of the first algorithm is also given where different multiplicities are consider for each interpolation point. Next, we proposed another extension of the standard Krylov subspace method for Multiple-Input Multiple-Output (MIMO) systems, which is the global Krylov subspace, and we obtained also some equations that describe this process. Finally, an extended block Lanczos method is introduced and new algebraic properties for this algorithm are also given. The accuracy and the efficiency of all proposed algorithms when applied to model order reduction problem are tested by means of different numerical experiments that use a collection of well known benchmark examples.

Cette thèse aborde le processus ponctuel déterminantal, un modèle probabiliste qui capture la répulsion entre les points d’un certain espace. Celle-ci est déterminée par une matrice de similarité, la matrice noyau du processus, qui spécifie quels points sont les plus similaires et donc moins susceptibles de figurer dans un même sous-ensemble. Contrairement à la sélection aléatoire uniforme, ce processus ponctuel privilégie les sous-ensembles qui contiennent des points diversifiés et hétérogènes. La notion de diversité acquiert une importante grandissante au sein de sciences comme la médecine, la sociologie, les sciences forensiques et les sciences comportementales. Le processus ponctuel déterminantal offre donc une alternative aux traditionnelles méthodes d’échantillonnage en tenant compte de la diversité des éléments choisis. Actuellement, il est déjà très utilisé en apprentissage automatique comme modèle de sélection de sous-ensembles. Son application en statistique est illustrée par trois articles. Le premier article aborde le partitionnement de données effectué par un algorithme répété un grand nombre de fois sur les mêmes données, le partitionnement par consensus. On montre qu’en utilisant le processus ponctuel déterminantal pour sélectionner les points initiaux de l’algorithme, la partition de données finale a une qualité supérieure à celle que l’on obtient en sélectionnant les points de façon uniforme. Le deuxième article étend la méthodologie du premier article aux données ayant un grand nombre d’observations. Ce cas impose un effort computationnel additionnel, étant donné que la sélection de points par le processus ponctuel déterminantal passe par la décomposition spectrale de la matrice de similarité qui, dans ce cas-ci, est de grande taille. On présente deux approches différentes pour résoudre ce problème. On montre que les résultats obtenus par ces deux approches sont meilleurs que ceux obtenus avec un partitionnement de données basé sur une sélection uniforme de points. Le troisième article présente le problème de sélection de variables en régression linéaire et logistique face à un nombre élevé de covariables par une approche bayésienne. La sélection de variables est faite en recourant aux méthodes de Monte Carlo par chaînes de Markov, en utilisant l’algorithme de Metropolis-Hastings. On montre qu’en choisissant le processus ponctuel déterminantal comme loi a priori de l’espace des modèles, le sous-ensemble final de variables est meilleur que celui que l’on obtient avec une loi a priori uniforme. / This thesis presents the determinantal point process, a probabilistic model that captures repulsion between points of a certain space. This repulsion is encompassed by a similarity matrix, the kernel matrix, which selects which points are more similar and then less likely to appear in the same subset. This point process gives more weight to subsets characterized by a larger diversity of its elements, which is not the case with the traditional uniform random sampling. Diversity has become a key concept in domains such as medicine, sociology, forensic sciences and behavioral sciences. The determinantal point process is considered a promising alternative to traditional sampling methods, since it takes into account the diversity of selected elements. It is already actively used in machine learning as a subset selection method. Its application in statistics is illustrated with three papers. The first paper presents the consensus clustering, which consists in running a clustering algorithm on the same data, a large number of times. To sample the initials points of the algorithm, we propose the determinantal point process as a sampling method instead of a uniform random sampling and show that the former option produces better clustering results. The second paper extends the methodology developed in the first paper to large-data. Such datasets impose a computational burden since sampling with the determinantal point process is based on the spectral decomposition of the large kernel matrix. We introduce two methods to deal with this issue. These methods also produce better clustering results than consensus clustering based on a uniform sampling of initial points. The third paper addresses the problem of variable selection for the linear model and the logistic regression, when the number of predictors is large. A Bayesian approach is adopted, using Markov Chain Monte Carlo methods with Metropolis-Hasting algorithm. We show that setting the determinantal point process as the prior distribution for the model space selects a better final model than the model selected by a uniform prior on the model space.