Reliable computation of robust response tori on the verge of breakdown

We prove the existence and local uniqueness of invariant tori on the verge of breakdown for two systems: the quasi-periodically driven logistic map and the quasi-periodically forced standard map. These systems exemplify two scenarios: the Heagy-Hammel route for the creation of strange non- chaotic attractors and the nonsmooth bifurcation of saddle invariant tori. Our proofs are computer- assisted and are based on a tailored version of the Newton-Kantorovich theorem. The proofs cannot be performed using classical perturbation theory because the two scenarios are very far from the perturbative regime, and fundamental hypotheses such as reducibility or hyperbolicity either do not hold or are very close to failing. Our proofs are based on a reliable computation of the invariant tori and a careful study of their dynamical properties, leading to the rigorous validation of the numerical results with our novel computational techniques.

Computer-aided system for morphometric mandibular index computation (Using dental panoramic radiographs)

Objective: We propose and validate a computer aided system to measure three different mandibular indexes: cortical width, panoramic mandibular index and, mandibular alveolar bone resorption index. Study Design: Repeatability and reproducibility of the measurements are analyzed and compared to the manual estimation of the same indexes. Results: The proposed computerized system exhibits superior repeatability and reproducibility rates compared to standard manual methods. Moreover, the time required to perform the measurements using the proposed method is negligible compared to perform the measurements manually. Conclusions: We have proposed a very user friendly computerized method to measure three different morphometric mandibular indexes. From the results we can conclude that the system provides a practical manner to perform these measurements. It does not require an expert examiner and does not take more than 16 seconds per analysis. Thus, it may be suitable to diagnose osteoporosis using dental panoramic radiographs

The Reality of Neandertal Symbolic Behavior at the Grotte du Renne, Arcy-sur-Cure, France

The question of whether symbolically mediated behavior is exclusive to modern humans or shared with anatomically archaic populations such as the Neandertals is hotly debated. At the Grotte du Renne, Arcy-sur-Cure, France, the Châtelperronian levels contain Neandertal remains and large numbers of personal ornaments, decorated bone tools and colorants, but it has been suggested that this association reflects intrusion of the symbolic artifacts from the overlying Protoaurignacian and/or of the Neandertal remains from the underlying Mousterian.

On the computation of reducible invariant tori on a parallel computer

We present an algorithm for the computation of reducible invariant tori of discrete dynamical systems that is suitable for tori of dimensions larger than 1. It is based on a quadratically convergent scheme that approximates, at the same time, the Fourier series of the torus, its Floquet transformation, and its Floquet matrix. The Floquet matrix describes the linearization of the dynamics around the torus and, hence, its linear stability. The algorithm presents a high degree of parallelism, and the computational effort grows linearly with the number of Fourier modes needed to represent the solution. For these reasons it is a very good option to compute quasi-periodic solutions with several basic frequencies. The paper includes some examples (flows) to show the efficiency of the method in a parallel computer. In these flows we compute invariant tori of dimensions up to 5, by taking suitable sections.

Fast and Rigorous Computation of Gene and Pathway Scores from SNP-Based Summary Statistics.

Integrating single nucleotide polymorphism (SNP) p-values from genome-wide association studies (GWAS) across genes and pathways is a strategy to improve statistical power and gain biological insight. Here, we present Pascal (Pathway scoring algorithm), a powerful tool for computing gene and pathway scores from SNP-phenotype association summary statistics. For gene score computation, we implemented analytic and efficient numerical solutions to calculate test statistics. We examined in particular the sum and the maximum of chi-squared statistics, which measure the strongest and the average association signals per gene, respectively. For pathway scoring, we use a modified Fisher method, which offers not only significant power improvement over more traditional enrichment strategies, but also eliminates the problem of arbitrary threshold selection inherent in any binary membership based pathway enrichment approach. We demonstrate the marked increase in power by analyzing summary statistics from dozens of large meta-studies for various traits. Our extensive testing indicates that our method not only excels in rigorous type I error control, but also results in more biologically meaningful discoveries.

Monte Carlo derivation of filtered tungsten anode X-ray spectra for dose computation in digital mammography

Abstract Objective: Derive filtered tungsten X-ray spectra used in digital mammography systems by means of Monte Carlo simulations. Materials and Methods: Filtered spectra for rhodium filter were obtained for tube potentials between 26 and 32 kV. The half-value layer (HVL) of simulated filtered spectra were compared with those obtained experimentally with a solid state detector Unfors model 8202031-H Xi R/F & MAM Detector Platinum and 8201023-C Xi Base unit Platinum Plus w mAs in a Hologic Selenia Dimensions system using a direct radiography mode. Results: Calculated HVL values showed good agreement as compared with those obtained experimentally. The greatest relative difference between the Monte Carlo calculated HVL values and experimental HVL values was 4%. Conclusion: The results show that the filtered tungsten anode X-ray spectra and the EGSnrc Monte Carlo code can be used for mean glandular dose determination in mammography.

Optimizing Customer Energy Invoice Calculation with Parallel Computation

Diplomityön tarkoituksena on optimoida asiakkaiden sähkölaskun laskeminen hajautetun laskennan avulla. Älykkäiden etäluettavien energiamittareiden tullessa jokaiseen kotitalouteen, energiayhtiöt velvoitetaan laskemaan asiakkaiden sähkölaskut tuntiperusteiseen mittaustietoon perustuen. Kasvava tiedonmäärä lisää myös tarvittavien laskutehtävien määrää. Työssä arvioidaan vaihtoehtoja hajautetun laskennan toteuttamiseksi ja luodaan tarkempi katsaus pilvilaskennan mahdollisuuksiin. Lisäksi ajettiin simulaatioita, joiden avulla arvioitiin rinnakkaislaskennan ja peräkkäislaskennan eroja. Sähkölaskujen oikeinlaskemisen tueksi kehitettiin mittauspuu-algoritmi.

Potential and Challenges of Analog Reconfigurable Computation in Modern and Future CMOS

In this work, the feasibility of the floating-gate technology in analog computing platforms in a scaled down general-purpose CMOS technology is considered. When the technology is scaled down the performance of analog circuits tends to get worse because the process parameters are optimized for digital transistors and the scaling involves the reduction of supply voltages. Generally, the challenge in analog circuit design is that all salient design metrics such as power, area, bandwidth and accuracy are interrelated. Furthermore, poor flexibility, i.e. lack of reconfigurability, the reuse of IP etc., can be considered the most severe weakness of analog hardware. On this account, digital calibration schemes are often required for improved performance or yield enhancement, whereas high flexibility/reconfigurability can not be easily achieved. Here, it is discussed whether it is possible to work around these obstacles by using floating-gate transistors (FGTs), and analyze problems associated with the practical implementation. FGT technology is attractive because it is electrically programmable and also features a charge-based built-in non-volatile memory. Apart from being ideal for canceling the circuit non-idealities due to process variations, the FGTs can also be used as computational or adaptive elements in analog circuits. The nominal gate oxide thickness in the deep sub-micron (DSM) processes is too thin to support robust charge retention and consequently the FGT becomes leaky. In principle, non-leaky FGTs can be implemented in a scaled down process without any special masks by using “double”-oxide transistors intended for providing devices that operate with higher supply voltages than general purpose devices. However, in practice the technology scaling poses several challenges which are addressed in this thesis. To provide a sufficiently wide-ranging survey, six prototype chips with varying complexity were implemented in four different DSM process nodes and investigated from this perspective. The focus is on non-leaky FGTs, but the presented autozeroing floating-gate amplifier (AFGA) demonstrates that leaky FGTs may also find a use. The simplest test structures contain only a few transistors, whereas the most complex experimental chip is an implementation of a spiking neural network (SNN) which comprises thousands of active and passive devices. More precisely, it is a fully connected (256 FGT synapses) two-layer spiking neural network (SNN), where the adaptive properties of FGT are taken advantage of. A compact realization of Spike Timing Dependent Plasticity (STDP) within the SNN is one of the key contributions of this thesis. Finally, the considerations in this thesis extend beyond CMOS to emerging nanodevices. To this end, one promising emerging nanoscale circuit element - memristor - is reviewed and its applicability for analog processing is considered. Furthermore, it is discussed how the FGT technology can be used to prototype computation paradigms compatible with these emerging two-terminal nanoscale devices in a mature and widely available CMOS technology.

Spectral and symbolic analysis of the effect of gender and postural change on cardiac autonomic modulation in healthy elderly subjects

The objective of this study was to use linear and non-linear methods to investigate cardiac autonomic modulation in healthy elderly men and women in response to a postural change from the supine to the standing position. Fourteen men (66.1 ± 3.5 years) and 10 women (65.3 ± 3.3 years) were evaluated. Beat-to-beat heart rate was recorded in the supine and standing positions. Heart rate variability was studied by spectral analysis, including both low (LFnu-cardiac sympathetic modulation (CSM) indicator) and high (HFnu-cardiac vagal modulation (CVM) indicator) frequencies in normalized units as well as the low frequency/high frequency (LF/HF) ratio. Symbolic analysis was performed using the following indexes: 0V% (CSM indicator), 1V% (CSM and CVM indicators), 2LV% (predominantly CVM indicator) and 2ULV% (CVM indicator). Shannon entropy was also calculated. Men presented higher LFnu and LF/HF ratio and lower HFnu and 1V% symbolic index (57.56, 4.14, 40.53, 45.96, respectively) than women (24.60, 0.45, 72.47, 52.69, respectively) in the supine position. Shannon entropy was higher among men (3.53) than among women (3.33) in the standing position, and also increased according to postural change in men (3.25; 3.53). During postural change, the LFnu (24.60; 49.85) and LF/HF ratio (0.45; 1.72) increased, with a concomitant decrease in HFnu (72.47; 47.56) and 2LV% (14.10; 6.95) in women. Women presented increased CSM in response to postural change and had higher CVM and lower CSM than men in the supine position. In conclusion, women in the age range studied presented a more appropriate response to a postural change than men, suggesting that cardiac autonomic modulation may be better preserved in women than in men.

Computation and Analysis of Multiple Structural-Change Models

In a recent paper, Bai and Perron (1998) considered theoretical issues related to the limiting distribution of estimators and test statistics in the linear model with multiple structural changes. In this companion paper, we consider practical issues for the empirical applications of the procedures. We first address the problem of estimation of the break dates and present an efficient algorithm to obtain global minimizers of the sum of squared residuals. This algorithm is based on the principle of dynamic programming and requires at most least-squares operations of order O(T 2) for any number of breaks. Our method can be applied to both pure and partial structural-change models. Secondly, we consider the problem of forming confidence intervals for the break dates under various hypotheses about the structure of the data and the errors across segments. Third, we address the issue of testing for structural changes under very general conditions on the data and the errors. Fourth, we address the issue of estimating the number of breaks. We present simulation results pertaining to the behavior of the estimators and tests in finite samples. Finally, a few empirical applications are presented to illustrate the usefulness of the procedures. All methods discussed are implemented in a GAUSS program available upon request for non-profit academic use.

Categorical quantum computation

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Reliable computation for geometric models

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Practical and Foundational Aspects of Secure Computation

Il y a des problemes qui semblent impossible a resoudre sans l'utilisation d'un tiers parti honnete. Comment est-ce que deux millionnaires peuvent savoir qui est le plus riche sans dire a l'autre la valeur de ses biens ? Que peut-on faire pour prevenir les collisions de satellites quand les trajectoires sont secretes ? Comment est-ce que les chercheurs peuvent apprendre les liens entre des medicaments et des maladies sans compromettre les droits prives du patient ? Comment est-ce qu'une organisation peut ecmpecher le gouvernement d'abuser de l'information dont il dispose en sachant que l'organisation doit n'avoir aucun acces a cette information ? Le Calcul multiparti, une branche de la cryptographie, etudie comment creer des protocoles pour realiser de telles taches sans l'utilisation d'un tiers parti honnete. Les protocoles doivent etre prives, corrects, efficaces et robustes. Un protocole est prive si un adversaire n'apprend rien de plus que ce que lui donnerait un tiers parti honnete. Un protocole est correct si un joueur honnete recoit ce que lui donnerait un tiers parti honnete. Un protocole devrait bien sur etre efficace. Etre robuste correspond au fait qu'un protocole marche meme si un petit ensemble des joueurs triche. On demontre que sous l'hypothese d'un canal de diusion simultane on peut echanger la robustesse pour la validite et le fait d'etre prive contre certains ensembles d'adversaires. Le calcul multiparti a quatre outils de base : le transfert inconscient, la mise en gage, le partage de secret et le brouillage de circuit. Les protocoles du calcul multiparti peuvent etre construits avec uniquements ces outils. On peut aussi construire les protocoles a partir d'hypoth eses calculatoires. Les protocoles construits a partir de ces outils sont souples et peuvent resister aux changements technologiques et a des ameliorations algorithmiques. Nous nous demandons si l'efficacite necessite des hypotheses de calcul. Nous demontrons que ce n'est pas le cas en construisant des protocoles efficaces a partir de ces outils de base. Cette these est constitue de quatre articles rediges en collaboration avec d'autres chercheurs. Ceci constitue la partie mature de ma recherche et sont mes contributions principales au cours de cette periode de temps. Dans le premier ouvrage presente dans cette these, nous etudions la capacite de mise en gage des canaux bruites. Nous demontrons tout d'abord une limite inferieure stricte qui implique que contrairement au transfert inconscient, il n'existe aucun protocole de taux constant pour les mises en gage de bit. Nous demontrons ensuite que, en limitant la facon dont les engagements peuvent etre ouverts, nous pouvons faire mieux et meme un taux constant dans certains cas. Ceci est fait en exploitant la notion de cover-free families . Dans le second article, nous demontrons que pour certains problemes, il existe un echange entre robustesse, la validite et le prive. Il s'effectue en utilisant le partage de secret veriable, une preuve a divulgation nulle, le concept de fantomes et une technique que nous appelons les balles et les bacs. Dans notre troisieme contribution, nous demontrons qu'un grand nombre de protocoles dans la litterature basee sur des hypotheses de calcul peuvent etre instancies a partir d'une primitive appelee Transfert Inconscient Veriable, via le concept de Transfert Inconscient Generalise. Le protocole utilise le partage de secret comme outils de base. Dans la derniere publication, nous counstruisons un protocole efficace avec un nombre constant de rondes pour le calcul a deux parties. L'efficacite du protocole derive du fait qu'on remplace le coeur d'un protocole standard par une primitive qui fonctionne plus ou moins bien mais qui est tres peu couteux. On protege le protocole contre les defauts en utilisant le concept de privacy amplication .

The typic in Kant’s critique of practical reason : moral judgment and symbolic representation

Comment pouvons-nous représenter un principe moral universel de manière à le rendre applicable à des cas concrets ? Ce problème revêt une forme aiguë dans la philosophie morale d’Emmanuel Kant (1724-1804), tout particulièrement dans sa théorie du jugement moral, car il soutient que l’on doit appliquer la loi morale « suprasensible » à des actions dans le monde sensible afin de déterminer celles-ci comme moralement bonnes ou mauvaises. Kant aborde ce problème dans un chapitre de la Critique de la raison pratique (1788) intitulé « De la typique de la faculté de juger pratique pure » (KpV 5: 67-71). La première partie de la thèse vise à fournir un commentaire compréhensif et détaillé de ce texte important, mais trop peu étudié. Étant donné que la loi morale, en tant qu’Idée suprasensible de la raison, ne peut pas être appliquée directement à des actions dans l’intuition sensible, Kant a recours à une forme particulière de représentation indirecte et symbolique. Sa solution inédite consiste à fournir la faculté de juger avec un « type [Typus] », ou analogue formel, de la loi morale. Ce type est la loi de la causalité naturelle : en tant que loi, il sert d’étalon formel pour tester l’universalisabilité des maximes ; et, en tant que loi de la nature, il peut aussi s’appliquer à toute action dans l’expérience sensible. Dès lors, le jugement moral s’effectue par le biais d’une expérience de pensée dans laquelle on se demande si l’on peut vouloir que sa maxime devienne une loi universelle d’une nature contrefactuelle dont on ferait soi-même partie. Cette expérience de pensée fonctionne comme une « épreuve [Probe] » de la forme des maximes et, par ce moyen, du statut moral des actions. Kant soutient que tout un chacun, même « l’entendement le plus commun », emploie cette procédure pour l’appréciation morale. De plus, la typique prémunit contre deux menaces à l’éthique rationaliste de Kant, à savoir l’empirisme (c’est-à-dire le conséquentialisme) et le mysticisme. La seconde partie de la thèse se penche sur l’indication de Kant que la typique « ne sert que comme un symbole ». Un bon nombre de commentateurs ont voulu assimiler la typique à la notion d’« hypotypose symbolique » présentée dans le § 59 de la Critique de la faculté de juger (1790). La typique serait un processus de symbolisation esthétique consistant à présenter, de façon indirecte, la représentation abstraite de la loi morale sous la forme d’un symbole concret et intuitif. Dans un premier chapitre, cette interprétation est présentée et soumise à un examen critique qui cherche à montrer qu’elle est erronée et peu judicieuse. Dans le second chapitre, nous poursuivons une voie d’interprétation jusqu’ici ignorée, montrant que la typique a de plus grandes continuités avec la notion d’« anthropomorphisme symbolique », une procédure strictement analogique introduite auparavant dans les Prolégomènes (1783). Nous en concluons, d’une part, que la typique fut un moment décisif dans l’évolution de la théorie kantienne de la représentation symbolique et que, d’autre part, elle marque la réalisation, chez Kant, d’une conception proprement critique de la nature et de la morale comme deux sphères distinctes, dont la médiation s’opère par le biais des concepts de loi et de conformité à la loi (Gesetzmässigkeit). En un mot, la typique s’avère l’instrument par excellence du « rationalisme de la faculté de juger ».

Distributed conditional computation

L'objectif de cette thèse est de présenter différentes applications du programme de recherche de calcul conditionnel distribué. On espère que ces applications, ainsi que la théorie présentée ici, mènera à une solution générale du problème d'intelligence artificielle, en particulier en ce qui a trait à la nécessité d'efficience. La vision du calcul conditionnel distribué consiste à accélérer l'évaluation et l'entraînement de modèles profonds, ce qui est très différent de l'objectif usuel d'améliorer sa capacité de généralisation et d'optimisation. Le travail présenté ici a des liens étroits avec les modèles de type mélange d'experts. Dans le chapitre 2, nous présentons un nouvel algorithme d'apprentissage profond qui utilise une forme simple d'apprentissage par renforcement sur un modèle d'arbre de décisions à base de réseau de neurones. Nous démontrons la nécessité d'une contrainte d'équilibre pour maintenir la distribution d'exemples aux experts uniforme et empêcher les monopoles. Pour rendre le calcul efficient, l'entrainement et l'évaluation sont contraints à être éparse en utilisant un routeur échantillonnant des experts d'une distribution multinomiale étant donné un exemple. Dans le chapitre 3, nous présentons un nouveau modèle profond constitué d'une représentation éparse divisée en segments d'experts. Un modèle de langue à base de réseau de neurones est construit à partir des transformations éparses entre ces segments. L'opération éparse par bloc est implémentée pour utilisation sur des cartes graphiques. Sa vitesse est comparée à deux opérations denses du même calibre pour démontrer le gain réel de calcul qui peut être obtenu. Un modèle profond utilisant des opérations éparses contrôlées par un routeur distinct des experts est entraîné sur un ensemble de données d'un milliard de mots. Un nouvel algorithme de partitionnement de données est appliqué sur un ensemble de mots pour hiérarchiser la couche de sortie d'un modèle de langage, la rendant ainsi beaucoup plus efficiente. Le travail présenté dans cette thèse est au centre de la vision de calcul conditionnel distribué émis par Yoshua Bengio. Elle tente d'appliquer la recherche dans le domaine des mélanges d'experts aux modèles profonds pour améliorer leur vitesse ainsi que leur capacité d'optimisation. Nous croyons que la théorie et les expériences de cette thèse sont une étape importante sur la voie du calcul conditionnel distribué car elle cadre bien le problème, surtout en ce qui concerne la compétitivité des systèmes d'experts.