Matrix Decomposition Methods for Data Mining : Computational Complexity and Algorithms

Matrix decompositions, where a given matrix is represented as a product of two other matrices, are regularly used in data mining. Most matrix decompositions have their roots in linear algebra, but the needs of data mining are not always those of linear algebra. In data mining one needs to have results that are interpretable -- and what is considered interpretable in data mining can be very different to what is considered interpretable in linear algebra. --- The purpose of this thesis is to study matrix decompositions that directly address the issue of interpretability. An example is a decomposition of binary matrices where the factor matrices are assumed to be binary and the matrix multiplication is Boolean. The restriction to binary factor matrices increases interpretability -- factor matrices are of the same type as the original matrix -- and allows the use of Boolean matrix multiplication, which is often more intuitive than normal matrix multiplication with binary matrices. Also several other decomposition methods are described, and the computational complexity of computing them is studied together with the hardness of approximating the related optimization problems. Based on these studies, algorithms for constructing the decompositions are proposed. Constructing the decompositions turns out to be computationally hard, and the proposed algorithms are mostly based on various heuristics. Nevertheless, the algorithms are shown to be capable of finding good results in empirical experiments conducted with both synthetic and real-world data.

Computational fluid-structure interaction methods for simulation of inflatable aerodynamic decelerators

Inflatable aerodynamic decelerators have potential advantages for planetary re-entry in robotic and human exploration missions. It is theorized that volume-mass characteristics of these decelerators are superior to those of common supersonic/subsonic parachutes and after deployment they may suffer no instabilities at high Mach numbers. A high fidelity computational fluid-structure interaction model is employed to investigate the behavior of tension cone inflatable aeroshells at supersonic speeds up to Mach 2.0. The computational framework targets the large displacements regime encountered during the inflation of the decelerator using fast level set techniques to incorporate boundary conditions of the moving structure. The preliminary results indicate large but steady aeroshell displacement with rich dynamics, including buckling of the inflatable torus that maintains the decelerator open under normal operational conditions, owing to interactions with the turbulent wake. Copyright © 2009 by the American Institute of Aeronautics and Astronautics, Inc.

Combustion rumble prediction with integrated computational-fluid-dynamics/ low-order-model methods

The pressure oscillation within combustion chambers of aeroengines and industrial gas turbines is a major technical challenge to the development of high-performance and low-emission propulsion systems. In this paper, an approach integrating computational fluid dynamics and one-dimensional linear stability analysis is developed to predict the modes of oscillation in a combustor and their frequencies and growth rates. Linear acoustic theory was used to describe the acoustic waves propagating upstream and downstream of the combustion zone, which enables the computational fluid dynamics calculation to be efficiently concentrated on the combustion zone. A combustion oscillation was found to occur with its predicted frequency in agreement with experimental measurements. Furthermore, results from the computational fluid dynamics calculation provide the flame transfer function to describe unsteady heat release rate. Departures from ideal one-dimensional flows are described by shape factors. Combined with this information, low-order models can work out the possible oscillation modes and their initial growth rates. The approach developed here can be used in more general situations for the analysis of combustion oscillations. Copyright © 2012 by the American Institute of Aeronautics and Astronautics, Inc. All rights reserved.

Finite volume methods applied to the computational modelling of welding phenomena

This paper presents the computational modelling of welding phenomena within a versatile numerical framework. The framework embraces models from both the fields of computational fluid dynamics (CFD) and computational solid mechanics (CSM). With regard to the CFD modelling of the weld pool fluid dynamics, heat transfer and phase change, cell-centred finite volume (FV) methods are employed. Additionally, novel vertex-based FV methods are employed with regard to the elasto-plastic deformation associated with the CSM. The FV methods are included within an integrated modelling framework, PHYSICA, which can be readily applied to unstructured meshes. The modelling techniques are validated against a variety of reference solutions.

Computational scheduling methods for integrating plug-in electric vehicles with power systems: a review

Traditional internal combustion engine vehicles are a major contributor to global greenhouse gas emissions and other air pollutants, such as particulate matter and nitrogen oxides. If the tail pipe point emissions could be managed centrally without reducing the commercial and personal user functionalities, then one of the most attractive solutions for achieving a significant reduction of emissions in the transport sector would be the mass deployment of electric vehicles. Though electric vehicle sales are still hindered by battery performance, cost and a few other technological bottlenecks, focused commercialisation and support from government policies are encouraging large scale electric vehicle adoptions. The mass proliferation of plug-in electric vehicles is likely to bring a significant additional electric load onto the grid creating a highly complex operational problem for power system operators. Electric vehicle batteries also have the ability to act as energy storage points on the distribution system. This double charge and storage impact of many uncontrollable small kW loads, as consumers will want maximum flexibility, on a distribution system which was originally not designed for such operations has the potential to be detrimental to grid balancing. Intelligent scheduling methods if established correctly could smoothly integrate electric vehicles onto the grid. Intelligent scheduling methods will help to avoid cycling of large combustion plants, using expensive fossil fuel peaking plant, match renewable generation to electric vehicle charging and not overload the distribution system causing a reduction in power quality. In this paper, a state-of-the-art review of scheduling methods to integrate plug-in electric vehicles are reviewed, examined and categorised based on their computational techniques. Thus, in addition to various existing approaches covering analytical scheduling, conventional optimisation methods (e.g. linear, non-linear mixed integer programming and dynamic programming), and game theory, meta-heuristic algorithms including genetic algorithm and particle swarm optimisation, are all comprehensively surveyed, offering a systematic reference for grid scheduling considering intelligent electric vehicle integration.

A tutorial on pseudospectral methods for computational optimal control

[English] This paper is a tutorial introduction to pseudospectral optimal control. With pseudospectral methods, a function is approximated as a linear combination of smooth basis functions, which are often chosen to be Legendre or Chebyshev polynomials. Collocation of the differential-algebraic equations is performed at orthogonal collocation points, which are selected to yield interpolation of high accuracy. Pseudospectral methods directly discretize the original optimal control problem to recast it into a nonlinear programming format. A numerical optimizer is then employed to find approximate local optimal solutions. The paper also briefly describes the functionality and implementation of PSOPT, an open source software package written in C++ that employs pseudospectral discretization methods to solve multi-phase optimal control problems. The software implements the Legendre and Chebyshev pseudospectral methods, and it has useful features such as automatic differentiation, sparsity detection, and automatic scaling. The use of pseudospectral methods is illustrated in two problems taken from the literature on computational optimal control. [Portuguese] Este artigo e um tutorial introdutorio sobre controle otimo pseudo-espectral. Em metodos pseudo-espectrais, uma funcao e aproximada como uma combinacao linear de funcoes de base suaves, tipicamente escolhidas como polinomios de Legendre ou Chebyshev. A colocacao de equacoes algebrico-diferenciais e realizada em pontos de colocacao ortogonal, que sao selecionados de modo a minimizar o erro de interpolacao. Metodos pseudoespectrais discretizam o problema de controle otimo original de modo a converte-lo em um problema de programa cao nao-linear. Um otimizador numerico e entao empregado para obter solucoes localmente otimas. Este artigo tambem descreve sucintamente a funcionalidade e a implementacao de um pacote computacional de codigo aberto escrito em C++ chamado PSOPT. Tal pacote emprega metodos de discretizacao pseudo-spectrais para resolver problemas de controle otimo com multiplas fase. O PSOPT permite a utilizacao de metodos de Legendre ou Chebyshev, e possui caractersticas uteis tais como diferenciacao automatica, deteccao de esparsidade e escalonamento automatico. O uso de metodos pseudo-espectrais e ilustrado em dois problemas retirados da literatura de controle otimo computacional.

Computational aspects of harmonic wavelet Galerkin methods and an application to a precipitation front propagation model

This article is dedicated to harmonic wavelet Galerkin methods for the solution of partial differential equations. Several variants of the method are proposed and analyzed, using the Burgers equation as a test model. The computational complexity can be reduced when the localization properties of the wavelets and restricted interactions between different scales are exploited. The resulting variants of the method have computational complexities ranging from O(N(3)) to O(N) (N being the space dimension) per time step. A pseudo-spectral wavelet scheme is also described and compared to the methods based on connection coefficients. The harmonic wavelet Galerkin scheme is applied to a nonlinear model for the propagation of precipitation fronts, with the front locations being exposed in the sizes of the localized wavelet coefficients. (C) 2011 Elsevier Ltd. All rights reserved.