Matrix-vector multiplication and triangular linear solver using GPGPU for symmetric positive definite matrices derived from elliptic equations

The modern GPUs are well suited for intensive computational tasks and massive parallel computation. Sparse matrix multiplication and linear triangular solver are the most important and heavily used kernels in scientific computation, and several challenges in developing a high performance kernel with the two modules is investigated. The main interest it to solve linear systems derived from the elliptic equations with triangular elements. The resulting linear system has a symmetric positive definite matrix. The sparse matrix is stored in the compressed sparse row (CSR) format. It is proposed a CUDA algorithm to execute the matrix vector multiplication using directly the CSR format. A dependence tree algorithm is used to determine which variables the linear triangular solver can determine in parallel. To increase the number of the parallel threads, a coloring graph algorithm is implemented to reorder the mesh numbering in a pre-processing phase. The proposed method is compared with parallel and serial available libraries. The results show that the proposed method improves the computation cost of the matrix vector multiplication. The pre-processing associated with the triangular solver needs to be executed just once in the proposed method. The conjugate gradient method was implemented and showed similar convergence rate for all the compared methods. The proposed method showed significant smaller execution time.

Effective response of a non-linear composite in external AC electric field

A general effective response is proposed for nonlinear composite media, which obey a current field relation of the form J = sigmaE + chi\E\(2) E when an external alternating current (AC) electrical field is applied. For a sinusoidal applied field with finite frequency omega, the effective constitutive relation between the current density and electric field can be defined as, = sigma(e) + chi(e) <\E(x, omega, t)\(2) E(x, omega, t)> + (. . .), where sigma(e) and chi(e) are the general effective linear and nonlinear conductive responses, respectively. The angled brackets <(. . .)> denotes the ensemble average. As two examples, we have investigated the cylindrical and spherical inclusions embedded in a host and also derived the formulae of the general effective linear and nonlinear conductive responses in dilute limit. For higher volume fraction of inclusions, we have proposed a nonlinear effective medium approximation (EMA) method to estimate the general effective response of nonlinear composites in external AC field. Furthermore, the effective nonlinear responses at harmonics are predicted by using the general effective response. (C) 2002 Elsevier Science B.V. All rights reserved.

Prematurely condensed chromosome fragments in human lymphocytes induced by high doses of high-linear-energy-transfer irradiation

This study provides a useful biodosimetry protocol for radiation accidents that involve high doses of heavy particle radiation. Human peripheral blood lymphocytes (PBLs) were irradiated in vitro with high doses (5–50 Gy) of charged heavy-ion particles (carbon ions, at an effective linear-energy-transfer (LET) of 34.6 keV/ m), and were then stimulated to obtain dividing cells. PBLs were treated with 100nMcalyculin A to force chromosomes to condense prematurely, and chromosome spreads were obtained and stained with Giemsa. The G2 prematurely condensed chromosome (G2-PCC) index and the number of G2-PCC including fragments (G2-PCC-Fs) per cell for each radiation dose point were scored. Dose-effect relationships were obtained by plotting the G2-PCC indices or G2-PCC-Fs numbers against radiation doses. The G2-PCC index was greater than 5% up to doses of 15 Gy; even after a 30Gy radiation dose, the index was 1 to 2%. At doses higher than 30 Gy, however, the G2-PCC indices were close to zero. The number of G2-PCC-Fs increased steeply for radiation doses up to 30 Gy at a rate of 1.07 Gy−1. At doses higher than 30 Gy, the numbers of G2-PCC-Fs could not be accurately indexed because of the limited numbers of cells for analysis. Therefore, the number of G2-PCC-Fs could be used to estimate radiation doses up to 30 Gy. In addition, a G2-PCC index close to zero could be used as an indicator for radiation doses greater than 40 Gy.

Effective response of nonlinear composite under external AC and DC electric field

A perturbation method is used to study effective response of nonlinear Kerr composites, which are subject to the constitutive relation of electric displacement and electric field, D-alpha = epsilon(alpha)E + chi(alpha)vertical bar E vertical bar(2)E. Under the external AC and DC electric field E-app = E-a (1 + sinwt), the effective nonlinear responses and local potentials are induced by the cubic nonlinearity of Kerr materials at all harmonics. As an example in three dimensions, we have investigated this kind of nonlinear composites with spherical inclusions embedded in a host. At all harmonic frequencies, the potentials in inclusion and host regions are derived. Furthermore, the formulae of the effective linear and nonlinear responses are given in the dilute limit.

Effective thermal conductivity of graded nonlinear composites with heat contact resistance

The perturbation expansion method is used to find the effective thermal conductivity of graded nonlinear composites having thermal contact resistance on the inclusion surface. As an example, we have studied the graded composites with cylindrical inclusions immersed in a homogeneous matrix. The thermal conductivity of the cylindrical inclusion is assumed to have a power-law profile of the radial distance r measured from its origin. For weakly nonlinear constitutive relations between the heat flow density q and the temperature field T, namely, q = -mu del T - chi vertical bar del T vertical bar(2) del T, in both the inclusion and the matrix regions, we have derived the temperature distributions using the perturbation expansion method. A nonlinear effective medium approximation of graded composites is proposed to estimate the effective linear and nonlinear thermal conductivities. by considering the temperature singularity on the inclusion surface due to the heat contact resistance. (c) 2006 Elsevier B.V. All rights reserved.

Black-box decomposition approach for computational hemodynamics: One-dimensional models

Increasing efforts exist in integrating different levels of detail in models of the cardiovascular system. For instance, one-dimensional representations are employed to model the systemic circulation. In this context, effective and black-box-type decomposition strategies for one-dimensional networks are needed, so as to: (i) employ domain decomposition strategies for large systemic models (1D-1D coupling) and (ii) provide the conceptual basis for dimensionally-heterogeneous representations (1D-3D coupling, among various possibilities). The strategy proposed in this article works for both of these two scenarios, though the several applications shown to illustrate its performance focus on the 1D-1D coupling case. A one-dimensional network is decomposed in such a way that each coupling point connects two (and not more) of the sub-networks. At each of the M connection points two unknowns are defined: the flow rate and pressure. These 2M unknowns are determined by 2M equations, since each sub-network provides one (non-linear) equation per coupling point. It is shown how to build the 2M x 2M non-linear system with arbitrary and independent choice of boundary conditions for each of the sub-networks. The idea is then to solve this non-linear system until convergence, which guarantees strong coupling of the complete network. In other words, if the non-linear solver converges at each time step, the solution coincides with what would be obtained by monolithically modeling the whole network. The decomposition thus imposes no stability restriction on the choice of the time step size. Effective iterative strategies for the non-linear system that preserve the black-box character of the decomposition are then explored. Several variants of matrix-free Broyden`s and Newton-GMRES algorithms are assessed as numerical solvers by comparing their performance on sub-critical wave propagation problems which range from academic test cases to realistic cardiovascular applications. A specific variant of Broyden`s algorithm is identified and recommended on the basis of its computer cost and reliability. (C) 2010 Elsevier B.V. All rights reserved.

Predictive control of a Boeing 747 aircraft using an FPGA

New embedded predictive control applications call for more eficient ways of solving quadratic programs (QPs) in order to meet demanding real-time, power and cost requirements. A single precision QP-on-a-chip controller is proposed, implemented in afield-programmable gate array (FPGA) with an iterative linear solver at its core. A novel offline scaling procedure is introduced to aid the convergence of the reduced precision solver. The feasibility of the proposed approach is demonstrated with a real-time hardware-in-the-loop (HIL) experimental setup where an ML605 FPGA board controls a nonlinear model of a Boeing 747 aircraft running on a desktop PC through an Ethernet link. Simulations show that the quality of the closed-loop control and accuracy of individual solutions is competitive with a conventional double precision controller solving linear systems using a Riccati recursion. © 2012 IFAC.

Improving parameter learning of Bayesian nets from incomplete data

This paper addresses the estimation of parameters of a Bayesian network from incomplete data. The task is usually tackled by running the Expectation-Maximization (EM) algorithm several times in order to obtain a high log-likelihood estimate. We argue that choosing the maximum log-likelihood estimate (as well as the maximum penalized log-likelihood and the maximum a posteriori estimate) has severe drawbacks, being affected both by overfitting and model uncertainty. Two ideas are discussed to overcome these issues: a maximum entropy approach and a Bayesian model averaging approach. Both ideas can be easily applied on top of EM, while the entropy idea can be also implemented in a more sophisticated way, through a dedicated non-linear solver. A vast set of experiments shows that these ideas produce significantly better estimates and inferences than the traditional and widely used maximum (penalized) log-likelihood and maximum a posteriori estimates. In particular, if EM is adopted as optimization engine, the model averaging approach is the best performing one; its performance is matched by the entropy approach when implemented using the non-linear solver. The results suggest that the applicability of these ideas is immediate (they are easy to implement and to integrate in currently available inference engines) and that they constitute a better way to learn Bayesian network parameters.

Improving sampling, optimization and feature extraction in Boltzmann machines

L’apprentissage supervisé de réseaux hiérarchiques à grande échelle connaît présentement un succès fulgurant. Malgré cette effervescence, l’apprentissage non-supervisé représente toujours, selon plusieurs chercheurs, un élément clé de l’Intelligence Artificielle, où les agents doivent apprendre à partir d’un nombre potentiellement limité de données. Cette thèse s’inscrit dans cette pensée et aborde divers sujets de recherche liés au problème d’estimation de densité par l’entremise des machines de Boltzmann (BM), modèles graphiques probabilistes au coeur de l’apprentissage profond. Nos contributions touchent les domaines de l’échantillonnage, l’estimation de fonctions de partition, l’optimisation ainsi que l’apprentissage de représentations invariantes. Cette thèse débute par l’exposition d’un nouvel algorithme d'échantillonnage adaptatif, qui ajuste (de fa ̧con automatique) la température des chaînes de Markov sous simulation, afin de maintenir une vitesse de convergence élevée tout au long de l’apprentissage. Lorsqu’utilisé dans le contexte de l’apprentissage par maximum de vraisemblance stochastique (SML), notre algorithme engendre une robustesse accrue face à la sélection du taux d’apprentissage, ainsi qu’une meilleure vitesse de convergence. Nos résultats sont présent ́es dans le domaine des BMs, mais la méthode est générale et applicable à l’apprentissage de tout modèle probabiliste exploitant l’échantillonnage par chaînes de Markov. Tandis que le gradient du maximum de vraisemblance peut-être approximé par échantillonnage, l’évaluation de la log-vraisemblance nécessite un estimé de la fonction de partition. Contrairement aux approches traditionnelles qui considèrent un modèle donné comme une boîte noire, nous proposons plutôt d’exploiter la dynamique de l’apprentissage en estimant les changements successifs de log-partition encourus à chaque mise à jour des paramètres. Le problème d’estimation est reformulé comme un problème d’inférence similaire au filtre de Kalman, mais sur un graphe bi-dimensionnel, où les dimensions correspondent aux axes du temps et au paramètre de température. Sur le thème de l’optimisation, nous présentons également un algorithme permettant d’appliquer, de manière efficace, le gradient naturel à des machines de Boltzmann comportant des milliers d’unités. Jusqu’à présent, son adoption était limitée par son haut coût computationel ainsi que sa demande en mémoire. Notre algorithme, Metric-Free Natural Gradient (MFNG), permet d’éviter le calcul explicite de la matrice d’information de Fisher (et son inverse) en exploitant un solveur linéaire combiné à un produit matrice-vecteur efficace. L’algorithme est prometteur: en terme du nombre d’évaluations de fonctions, MFNG converge plus rapidement que SML. Son implémentation demeure malheureusement inefficace en temps de calcul. Ces travaux explorent également les mécanismes sous-jacents à l’apprentissage de représentations invariantes. À cette fin, nous utilisons la famille de machines de Boltzmann restreintes “spike & slab” (ssRBM), que nous modifions afin de pouvoir modéliser des distributions binaires et parcimonieuses. Les variables latentes binaires de la ssRBM peuvent être rendues invariantes à un sous-espace vectoriel, en associant à chacune d’elles, un vecteur de variables latentes continues (dénommées “slabs”). Ceci se traduit par une invariance accrue au niveau de la représentation et un meilleur taux de classification lorsque peu de données étiquetées sont disponibles. Nous terminons cette thèse sur un sujet ambitieux: l’apprentissage de représentations pouvant séparer les facteurs de variations présents dans le signal d’entrée. Nous proposons une solution à base de ssRBM bilinéaire (avec deux groupes de facteurs latents) et formulons le problème comme l’un de “pooling” dans des sous-espaces vectoriels complémentaires.

Modelagem generalizada do problema de planejamento da expansão de sistemas de transmissão

Pós-graduação em Engenharia Elétrica - FEIS

Routing Algorithms for All-Optical Networks with Power Considerations: The Unicast Case

In this paper, we investigate the problem of routing connections in all-optical networks while allowing for degradation of routed signals by different optical components. To overcome the complexity of the problem, we divide it into two parts. First, we solve the pure RWA problem using fixed routes for every connection. Second, power assignment is accomplished by either using the smallest-gain first (SGF) heuristic or using a genetic algorithm. Numerical examples on a wide variety of networks show that (a) the number of connections established without considering the signal attenuation was most of the time greater than that achievable considering attenuation and (b) the genetic solution quality was much better than that of SGF, especially when the conflict graph of the connections generated by the linear solver is denser.

Effective contrast recovery in rapid dynamic near-infrared diffuse optical tomography using l(1)-norm-based linear image reconstruction method

Traditional image reconstruction methods in rapid dynamic diffuse optical tomography employ l(2)-norm-based regularization, which is known to remove the high-frequency components in the reconstructed images and make them appear smooth. The contrast recovery in these type of methods is typically dependent on the iterative nature of method employed, where the nonlinear iterative technique is known to perform better in comparison to linear techniques (noniterative) with a caveat that nonlinear techniques are computationally complex. Assuming that there is a linear dependency of solution between successive frames resulted in a linear inverse problem. This new framework with the combination of l(1)-norm based regularization can provide better robustness to noise and provide better contrast recovery compared to conventional l(2)-based techniques. Moreover, it is shown that the proposed l(1)-based technique is computationally efficient compared to its counterpart (l(2)-based one). The proposed framework requires a reasonably close estimate of the actual solution for the initial frame, and any suboptimal estimate leads to erroneous reconstruction results for the subsequent frames.

A regularized linear classifier for effective text classification

In document community support vector machines and naïve bayes classifier are known for their simplistic yet excellent performance. Normally the feature subsets used by these two approaches complement each other, however a little has been done to combine them. The essence of this paper is a linear classifier, very similar to these two. We propose a novel way of combining these two approaches, which synthesizes best of them into a hybrid model. We evaluate the proposed approach using 20ng dataset, and compare it with its counterparts. The efficacy of our results strongly corroborate the effectiveness of our approach.

Supergraph approach in a higher-order linear delta expansion calculation of the effective potential for F-type broken supersymmetry

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)