A deep scientific understanding of complex physical systems, such as the atmosphere, can be achieved neither by direct measurements nor by numerical simulations alone. Data assimilation is a rigorous procedure to fuse information from a priori knowledge of the system state, the physical laws governing the evolution of the system, and real measurements, all with associated error statistics. Data assimilation produces best (a posteriori) estimates of model states and parameter values, and results in considerably improved computer simulations. The acquisition and use of observations in data assimilation raises several important scientific questions related to optimal sensor network design, quantification of data impact, pruning redundant data, and identifying the most beneficial additional observations. These questions originate in operational data assimilation practice, and have started to attract considerable interest in the recent past. This dissertation advances the state of knowledge in four dimensional variational (4D-Var) - data assimilation by developing, implementing, and validating a novel computational framework for estimating observation impact and for optimizing sensor networks. The framework builds on the powerful methodologies of second-order adjoint modeling and the 4D-Var sensitivity equations. Efficient computational approaches for quantifying the observation impact include matrix free linear algebra algorithms and low-rank approximations of the sensitivities to observations. The sensor network configuration problem is formulated as a meta-optimization problem. Best values for parameters such as sensor location are obtained by optimizing a performance criterion, subject to the constraint posed by the 4D-Var optimization. Tractable computational solutions to this "optimization-constrained" optimization problem are provided. The results of this work can be directly applied to the deployment of intelligent sensors and adaptive observations, as well as to reducing the operating costs of measuring networks, while preserving their ability to capture the essential features of the system under consideration. / Ph. D.

[pt] Sabe-se que a maioria das estruturas reais estão sujeitas à diferentes casos de carregamentos, relacionadas à diferentes solicitações estruturais e à ação de forças naturais, como ventos e ondas. Neste contexto, é importante levar em consideração o efeito da maior quantidade de cenários possíveis que possam atuar em uma estrutura ao realizar um estudo de otimização topológica. A maneira tradicional de solução deste tipo de probema envolve uma análise caso a caso dos cenários, o que no contexto de um algoritmo de otimização estrutural requer a solução de um problema de elementos finitos para cada cenário em cada passo do algoritmo, ficando limitada pelo elevado custo computacional associado. Esta limitação abre espaço para abordagens baseadas em redução de dimensões como a aproximação estocástica e a decomposição em valores singulares. Este trabalho verifica a viabilidade do uso destes dois métodos na solução de problemas de otimização topológica estrutural com muitos casos de carga. Duas aplicações são apresentadas, otimização robusta e o problema de cargas dinâmicas usando o método do carregamento estático equivalente. Com isso, situações envolvendo carregamentos mais complexos podem ser estudadas através de algoritmos eficientes de otimização topológica. Para ambos os casos, são mostrados resultados comparando os resultados obtidos através da metodologia desenvolvida neste trabalho com resultados da literatura. / [en] It is known that most real structures are subject to different loading scenarios, related to different structural solicitations and the action of natural forces, such as winds and sea waves. In this context, it is important to consider the effect of the largest number of possible scenarios that can act on a structure when performing a topology optimization study. The traditional way of solving this type of problem involves a case-by-case analysis of the scenarios, which in the context of a structural optimization algorithm requires the solution of one finite element problem for each scenario and at each step of the algorithm, being limited by the high associated computational cost. This limitation leave room for approaches based on dimenson reduction such as stochastic approximation and decomposition into singular values. This work verifies the feasibility of using these two approaches to solve structural topology optimization problems with many load cases. Two applications are presented, robust optimization and the problem of dynamic loads using the equivalent static loading method. Thus, situations involving more complex loads can be studied through efficient topology optimization algorithms. For both cases, comparisons are established between the results obtained through the methodology developed in this work and the ones from the literature.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Cette thèse propose une technique innovante de diagnostic non invasive pour les systèmes piles à combustible. Cette technique s’appuie sur la mesure de la signature magnétique générée par ces systèmes. A l'aide de ces champs magnétiques externes, il est possible d'obtenir une cartographie de la densité de courant interne par résolution d'un problème inverse. Ce problème est néanmoins mal posé : la solution est non unique et est extrêmement sensible au bruit. Des techniques de régularisation ont ainsi été mises en place pour filtrer les erreurs de mesures et obtenir une solution physiquement acceptable. Afin d'augmenter la qualité de reconstruction des courants, nous avons conçu notre outil de diagnostic de manière à ce qu'il soit uniquement sensible aux défaillances de la pile (capteur de défauts). De plus, cette reconstruction se base sur un nombre extrêmement faible de mesures. Une telle approche facilite l'instrumentation du système et augmente la précision et la rapidité de celui-ci. La sensibilité de notre outil à certaines défaillances (assèchements, appauvrissement en réactifs, dégradations) est démontrée. / This thesis proposes a new non invasive technique for fuel cell diagnosis. This technique relies on the measurements of the magnetic field signature created by these systems. By solving an inverse problem, it is possible to get an internal current density map. However, the inverse problem is ill-posed: the solution is not unique and it is extremely sensitive to noise. Regularization techniques were used in order to filter out measurement errors and to obtain physical realistic solutions. In order to improve the quality of the current density estimators, a diagnostic tool was built which is only sensitive to faults occurring inside the fuel cell (fault sensor). More over, our approach is based on a very low number of measurements. Such technique simplifies the experimental setup and improves the accuracy and the speed of the diagnostic tool. The sensitivity of our tool to some faults (drying out, oxygen starvation and ageing) is demonstrated.

In many fields of science, engineering, and economics large amounts of data are stored and there is a need to analyze these data in order to extract information for various purposes. Data mining is a general concept involving different tools for performing this kind of analysis. The development of mathematical models and efficient algorithms is of key importance. In this thesis we discuss algorithms for the reduced rank regression problem and algorithms for the computation of the best multilinear rank approximation of tensors. The first two papers deal with the reduced rank regression problem, which is encountered in the field of state-space subspace system identification. More specifically the problem is \[ \min_{\rank(X) = k} \det (B - X A)(B - X A)\tp, \] where $A$ and $B$ are given matrices and we want to find $X$ under a certain rank condition that minimizes the determinant. This problem is not properly stated since it involves implicit assumptions on $A$ and $B$ so that $(B - X A)(B - X A)\tp$ is never singular. This deficiency of the determinant criterion is fixed by generalizing the minimization criterion to rank reduction and volume minimization of the objective matrix. The volume of a matrix is defined as the product of its nonzero singular values. We give an algorithm that solves the generalized problem and identify properties of the input and output signals causing a singular objective matrix. Classification problems occur in many applications. The task is to determine the label or class of an unknown object. The third paper concerns with classification of handwritten digits in the context of tensors or multidimensional data arrays. Tensor and multilinear algebra is an area that attracts more and more attention because of the multidimensional structure of the collected data in various applications. Two classification algorithms are given based on the higher order singular value decomposition (HOSVD). The main algorithm makes a data reduction using HOSVD of 98--99 \% prior the construction of the class models. The models are computed as a set of orthonormal bases spanning the dominant subspaces for the different classes. An unknown digit is expressed as a linear combination of the basis vectors. The resulting algorithm achieves 5\% in classification error with fairly low amount of computations. The remaining two papers discuss computational methods for the best multilinear rank approximation problem \[ \min_{\cB} \| \cA - \cB\| \] where $\cA$ is a given tensor and we seek the best low multilinear rank approximation tensor $\cB$. This is a generalization of the best low rank matrix approximation problem. It is well known that for matrices the solution is given by truncating the singular values in the singular value decomposition (SVD) of the matrix. But for tensors in general the truncated HOSVD does not give an optimal approximation. For example, a third order tensor $\cB \in \RR^{I \x J \x K}$ with rank$(\cB) = (r_1,r_2,r_3)$ can be written as the product \[ \cB = \tml{X,Y,Z}{\cC}, \qquad b_{ijk}=\sum_{\lambda,\mu,\nu} x_{i\lambda} y_{j\mu} z_{k\nu} c_{\lambda\mu\nu}, \] where $\cC \in \RR^{r_1 \x r_2 \x r_3}$ and $X \in \RR^{I \times r_1}$, $Y \in \RR^{J \times r_2}$, and $Z \in \RR^{K \times r_3}$ are matrices of full column rank. Since it is no restriction to assume that $X$, $Y$, and $Z$ have orthonormal columns and due to these constraints, the approximation problem can be considered as a nonlinear optimization problem defined on a product of Grassmann manifolds. We introduce novel techniques for multilinear algebraic manipulations enabling means for theoretical analysis and algorithmic implementation. These techniques are used to solve the approximation problem using Newton and Quasi-Newton methods specifically adapted to operate on products of Grassmann manifolds. The presented algorithms are suited for small, large and sparse problems and, when applied on difficult problems, they clearly outperform alternating least squares methods, which are standard in the field.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Cette thèse s’inscrit dans le contexte de l’analyse et de la classification de signaux électroencéphalogrammes (EEG) par des méthodes d’analyse discriminante. Ces signaux multi-capteurs qui sont, par nature, très fortement corrélés spatialement et temporellement sont considérés dans le plan temps-fréquence. En particulier, nous nous intéressons à des signaux de type potentiels évoqués qui sont bien représentés dans l’espace des ondelettes. Par la suite, nous considérons donc les signaux représentés par des coefficients multi-échelles et qui ont une structure matricielle électrodes × coefficients. Les signaux EEG sont considérés comme un mélange entre l’activité d’intérêt que l’on souhaite extraire et l’activité spontanée (ou "bruit de fond"), qui est largement prépondérante. La problématique principale est ici de distinguer des signaux issus de différentes conditions expérimentales (classes). Dans le cas binaire, nous nous focalisons sur l’approche probabiliste de l’analyse discriminante et des modèles de mélange gaussien sont considérés, décrivant dans chaque classe les signaux en termes de composantes fixes (moyenne) et aléatoires. Cette dernière, caractérisée par sa matrice de covariance, permet de modéliser différentes sources de variabilité. Essentielle à la mise en oeuvre de l’analyse discriminante, l’estimation de cette matrice (et de son inverse) peut être dégradée dans le cas de grandes dimensions et/ou de faibles échantillons d’apprentissage, cadre applicatif de cette thèse. Nous nous intéressons aux alternatives qui se basent sur la définition de modèle(s) de covariance(s) particulier(s) et qui permettent de réduire le nombre de paramètres à estimer. / The present thesis finds itself within the framework of analyzing and classifying electroencephalogram signals (EEG) using discriminant analysis. Those multi-sensor signals which are, by nature, highly correlated spatially and temporally are considered, in this work, in the timefrequency domain. In particular, we focus on low-frequency evoked-related potential-type signals (ERPs) that are well described in the wavelet domain. Thereafter, we will consider signals represented by multi-scale coefficients and that have a matrix structure electrodes × coefficients. Moreover, EEG signals are seen as a mixture between the signal of interest that we want to extract and spontaneous activity (also called "background noise") which is overriding. The main problematic is here to distinguish signals from different experimental conditions (class). In the binary case, we focus on the probabilistic approach of the discriminant analysis and Gaussian mixtures are used, describing in each class the signals in terms of fixed (mean) and random components. The latter, characterized by its covariance matrix, allow to model different variability sources. The estimation of this matrix (and of its inverse) is essential for the implementation of the discriminant analysis and can be deteriorated by high-dimensional data and/or by small learning samples, which is the application framework of this thesis. We are interested in alternatives that are based on specific covariance model(s) and that allow to decrease the number of parameters to estimate.

The work deals with automatic summarization of documents in HTML format. As a language of web documents, Czech language has been chosen. The project is focused on algorithms of text summarization. The work also includes document preprocessing for summarization and conversion of text into representation suitable for summarization algorithms. General text mining is also briefly discussed but the project is mainly focused on the automatic document summarization. Two simple summarization algorithms are introduced. Then, the main attention is paid to an advanced algorithm that uses latent semantic analysis. Result of the work is a design and implementation of summarization module for Python language. Final part of the work contains evaluation of summaries generated by implemented summarization methods and their subjective comparison of the author.

The present thesis considers the problem of reconstructing a function f that is defined on the d-dimensional unit sphere from its mean values along hyperplane sections. In case of the two-dimensional sphere, these plane sections are circles. In many tomographic applications, however, only limited data is available. Therefore, one is interested in the reconstruction of the function f from its mean values with respect to only some subfamily of all hyperplane sections of the sphere. Compared with the full data case, the limited data problem is more challenging and raises several questions. The first one is the injectivity, i.e., can any function be uniquely reconstructed from the available data? Further issues are the stability of the reconstruction, which is closely connected with a description of the range, as well as the demand for actual inversion methods or algorithms. We provide a detailed coverage and answers of these questions for different families of hyperplane sections of the sphere such as vertical slices, sections with hyperplanes through a common point and also incomplete great circles. Such reconstruction problems arise in various practical applications like Compton camera imaging, magnetic resonance imaging, photoacoustic tomography, Radar imaging or seismic imaging. Furthermore, we apply our findings about spherical means to the cone-beam transform and prove its singular value decomposition. / Die vorliegende Arbeit beschäftigt sich mit dem Problem der Rekonstruktion einer Funktion f, die auf der d-dimensionalen Einheitssphäre definiert ist, anhand ihrer Mittelwerte entlang von Schnitten mit Hyperebenen. Im Fall d=2 sind diese Schnitte genau die Kreise auf der Sphäre. In vielen tomografischen Anwendungen sind aber nur eingeschränkte Daten verfügbar. Deshalb besteht das Interesse an der Rekonstruktion der Funktion f nur anhand der Mittelwerte bestimmter Familien von Hyperebenen-Schnitten der Sphäre. Verglichen mit dem Fall vollständiger Daten birgt dieses Problem mehrere Herausforderungen und Fragen. Die erste ist die Injektivität, also können alle Funktionen anhand der gegebenen Daten eindeutig rekonstruiert werden? Weitere Punkte sind die die Frage nach der Stabilität der Rekonstruktion, welche eng mit einer Beschreibung der Bildmenge verbunden ist, sowie der praktische Bedarf an Rekonstruktionsmethoden und -algorithmen. Diese Arbeit gibt einen detaillierten Überblick und Antworten auf diese Fragen für verschiedene Familien von Hyperebenen-Schnitten, angefangen von vertikalen Schnitten über Schnitte mit Hyperebenen durch einen festen Punkt sowie Kreisbögen. Solche Rekonstruktionsprobleme treten in diversen Anwendungen auf wie der Bildgebung mittels Compton-Kamera, Magnetresonanztomografie, fotoakustischen Tomografie, Radar-Bildgebung sowie der Tomografie seismischer Wellen. Weiterhin nutzen wir unsere Ergebnisse über sphärische Mittelwerte, um eine Singulärwertzerlegung für die Kegelstrahltomografie zu zeigen.

Un préconditionneur à deux niveaux, reposant sur la technique d’accélération d’Aitken d’une suite de q vecteurs solutions de l’interface d’un pro- cessus itératif de Schwarz Additif Restreint, est conçu. Cette nouvelle technique, dénomée ARAS(q), utilise une approximation grossière de la solution sur l’interface. Différentes méthodes sont proposées, aboutissant au développement d’une tech- nique d’approximation par Décomposition en Valeures Singulières de la suite de vecteurs. Des implémentations parallèles des méthodes d’Aitken-Schwarz sont pro- posées et l’étude conduit à l’implémentation d’un code totalement algébrique, sur un ou deux niveaux de parallélisation MPI, écrit dans l’environnement de la biblio- thèque PETSc. Cette implémentation pleinement parallèle et algébrique procure un outil flexible pour la résolution de systèmes linéaires tels que ceux issus de la dif- férentiation automatique des solutions de Navier-Stokes dépendant des paramètres de la simulation / A two level preconditioner, based on the Aitken acceleration technique of a sequence of q interface’s solution vectors of the Restricted Additive Schwarz iterative process, is designed. This new technique, called ARAS(q), uses a coarse approximation of the solution on the interface. Different methods are discussed, leading to the development of an approximation technique by Singular Value De- composition of the sequence of vectors. Parallel implementations of Aitken-Schwarz methods are proposed, and the study leads to a fully algebraic one-level and two- level MPI implementation of ARAS(q) written into the PETSc library framework. This fully parallel and algebraic code gives an adaptive tool to solve linear systems such as those arising from automatic differentiation of compressible Navier-Stokes solution with respect to the simulation’s parameters