Perturbation, extraction and refinement of invariant pairs for matrix polynomials

Generalizing the notion of an eigenvector, invariant subspaces are frequently used in the context of linear eigenvalue problems, leading to conceptually elegant and numerically stable formulations in applications that require the computation of several eigenvalues and/or eigenvectors. Similar benefits can be expected for polynomial eigenvalue problems, for which the concept of an invariant subspace needs to be replaced by the concept of an invariant pair. Little has been known so far about numerical aspects of such invariant pairs. The aim of this paper is to fill this gap. The behavior of invariant pairs under perturbations of the matrix polynomial is studied and a first-order perturbation expansion is given. From a computational point of view, we investigate how to best extract invariant pairs from a linearization of the matrix polynomial. Moreover, we describe efficient refinement procedures directly based on the polynomial formulation. Numerical experiments with matrix polynomials from a number of applications demonstrate the effectiveness of our extraction and refinement procedures.

On the Kalman-Bucy filter with specified input

In a recent paper, Vathsal suggested that a new configuration had been obtained for linear filtering problems, which was distinctly different from the Kalman-Bucy filter. It is shown that this in fact is merely a special case of the filter with a specified input.

Conditioning of incremental variational data assimilation, with application to the Met Office system

Implementations of incremental variational data assimilation require the iterative minimization of a series of linear least-squares cost functions. The accuracy and speed with which these linear minimization problems can be solved is determined by the condition number of the Hessian of the problem. In this study, we examine how different components of the assimilation system influence this condition number. Theoretical bounds on the condition number for a single parameter system are presented and used to predict how the condition number is affected by the observation distribution and accuracy and by the specified lengthscales in the background error covariance matrix. The theoretical results are verified in the Met Office variational data assimilation system, using both pseudo-observations and real data.

Multi-Objective Pipe Smoothing Genetic Algorithm For Water Distribution Network Design

This paper describes the formulation of a Multi-objective Pipe Smoothing Genetic Algorithm (MOPSGA) and its application to the least cost water distribution network design problem. Evolutionary Algorithms have been widely utilised for the optimisation of both theoretical and real-world non-linear optimisation problems, including water system design and maintenance problems. In this work we present a pipe smoothing based approach to the creation and mutation of chromosomes which utilises engineering expertise with the view to increasing the performance of the algorithm whilst promoting engineering feasibility within the population of solutions. MOPSGA is based upon the standard Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and incorporates a modified population initialiser and mutation operator which directly targets elements of a network with the aim to increase network smoothness (in terms of progression from one diameter to the next) using network element awareness and an elementary heuristic. The pipe smoothing heuristic used in this algorithm is based upon a fundamental principle employed by water system engineers when designing water distribution pipe networks where the diameter of any pipe is never greater than the sum of the diameters of the pipes directly upstream resulting in the transition from large to small diameters from source to the extremities of the network. MOPSGA is assessed on a number of water distribution network benchmarks from the literature including some real-world based, large scale systems. The performance of MOPSGA is directly compared to that of NSGA-II with regard to solution quality, engineering feasibility (network smoothness) and computational efficiency. MOPSGA is shown to promote both engineering and hydraulic feasibility whilst attaining good infrastructure costs compared to NSGA-II.

Implementação paralela escalável e eficiente do algoritmo simplex padrão em arquitetura multicore

This work presents a scalable and efficient parallel implementation of the Standard Simplex algorithm in the multicore architecture to solve large scale linear programming problems. We present a general scheme explaining how each step of the standard Simplex algorithm was parallelized, indicating some important points of the parallel implementation. Performance analysis were conducted by comparing the sequential time using the Simplex tableau and the Simplex of the CPLEXR IBM. The experiments were executed on a shared memory machine with 24 cores. The scalability analysis was performed with problems of different dimensions, finding evidence that our parallel standard Simplex algorithm has a better parallel efficiency for problems with more variables than constraints. In comparison with CPLEXR , the proposed parallel algorithm achieved a efficiency of up to 16 times better

The strut-and-tie models in reinforced concrete structures analysed by a numerical technique

Os modelos de bielas e tirantes são procedimentos de análise apropriados para projetar elementos de concreto armado em casos de regiões onde há alterações geométricas ou concentrações de tensões, denominadas regiões D. Trata-se de bons modelos de representação da estrutura para avaliar melhor o seu comportamento estrutural e seu mecanismo resistente. O presente artigo aplica a técnica da otimização topológica para identificar o fluxo de tensões nas estruturas, definindo a configuração dos membros de bielas e tirantes, e quantifica seus valores para dimensionamento. Utilizam-se o método ESO, e uma variante desse, o SESO (Smoothing ESO) com o método dos elementos finitos em elasticidade plana. A filosofia do SESO baseia-se na observação de que se o elemento não for necessário à estrutura, sua contribuição de rigidez vai diminuindo progressivamente. Isto é, sua remoção é atenuada nos valores da matriz constitutiva, como se este estivesse em processo de danificação. Para validar a presente formulação, apresentam-se alguns exemplos numéricos onde se comparam suas respostas com as advindas de trabalhos científicos pioneiros sobre o assunto.

A metaheuristic to solve the transmission expansion planning

In this letter, a genetic algorithm (GA) is applied to solve - the static and multistage transmission expansion planning (TEP) problem. The characteristics of the proposed GA to solve the TEP problem are presented. Results using some known systems show that the proposed GA solves a smaller number of linear programming problems in order to find the optimal solutions and obtains a better solution for the multistage TEP problem.

On a regular convex solver potential for an elastic-damage constitutive model: a theoretical analysis

This work is related with the proposition of a so-called regular or convex solver potential to be used in numerical simulations involving a certain class of constitutive elastic-damage models. All the mathematical aspects involved are based on convex analysis, which is employed aiming a consistent variational formulation of the potential and its conjugate one. It is shown that the constitutive relations for the class of damage models here considered can be derived from the solver potentials by means of sub-differentials sets. The optimality conditions of the resulting minimisation problem represent in particular a linear complementarity problem. Finally, a simple example is present in order to illustrate the possible integration errors that can be generated when finite step analysis is performed. (C) 2003 Elsevier Ltd. All rights reserved.

An implementation of modified scatter search algorithm to transmission expansion planning

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Branch and bound algorithm for transmission network expansion planning using DC model

This paper presents an algorithm to solve the network transmission system expansion planning problem using the DC model which is a mixed non-linear integer programming problem. The major feature of this work is the use of a Branch-and-Bound (B&B) algorithm to directly solve mixed non-linear integer problems. An efficient interior point method is used to solve the non-linear programming problem at each node of the B&B tree. Tests with several known systems are presented to illustrate the performance of the proposed method. ©2007 IEEE.

An enhanced genetic algorithm to solve the static and multistage transmission network expansion planning

An enhanced genetic algorithm (EGA) is applied to solve the long-term transmission expansion planning (LTTEP) problem. The following characteristics of the proposed EGA to solve the static and multistage LTTEP problem are presented, (1) generation of an initial population using fast, efficient heuristic algorithms, (2) better implementation of the local improvement phase and (3) efficient solution of linear programming problems (LPs). Critical comparative analysis is made between the proposed genetic algorithm and traditional genetic algorithms. Results using some known systems show that the proposed EGA presented higher efficiency in solving the static and multistage LTTEP problem, solving a smaller number of linear programming problems to find the optimal solutions and thus finding a better solution to the multistage LTTEP problem. Copyright © 2012 Luis A. Gallego et al.

Planejamento da expansão de sistemas de transmissão usando algoritmos tipo dual simplex especializados em uma estrutura branch and bound

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

Algoritmo genético na otimização do custo de colheita e transporte da cana-de-açúcar

Pós-graduação em Biometria - IBB

Aplicação de deconvolução homomórfica a dados sísmicos

Um registro sísmico é frequentemente representado como a convolução de um pulso-fonte com a resposta do meio ao impulso, relacionada ao caminho da propagação. O processo de separação destes dois componentes da convolução é denominado deconvolução. Existe uma variedade de aproximações para o desenvolvimento de uma deconvolução. Uma das mais comuns é o uso da filtragem linear inversa, ou seja, o processamento do sinal composto, através de um filtro linear, cuja resposta de frequência é a recíproca da transformada de Fourier de um dos componentes do sinal. Obviamente, a fim de usarmos a filtragem inversa, tais componentes devem ser conhecidas ou estimadas. Neste trabalho, tratamos da aplicação a sinais sísmicos, de uma técnica de deconvolução não linear, proposta por Oppenheim (1965), a qual utiliza a teoria de uma classe de sistemas não lineares, que satisfazem um princípio generalizado de superposição, denominados de sistemas homomórficos. Tais sistemas são particularmente úteis na separação de sinais que estão combinados através da operação de convolução. O algoritmo da deconvolução homomórfica transforma o processo de convolução em uma superposição aditiva de seus componentes, com o resultado de que partes simples podem ser separadas mais facilmente. Esta classe de técnicas de filtragem representa uma generalização dos problemas de filtragem linear. O presente método oferece a considerável vantagem de que não é necessário fazer qualquer suposição prévia sobre a natureza do pulso sísmico fonte, ou da resposta do meio ao impulso, não requerendo assim, as considerações usuais de que o pulso seja de fase-mínima e que a distribuição dos impulsos seja aleatória, embora a qualidade dos resultados obtidos pela análise homomórfica seja muito sensível à razão sinal/ruído, como demonstrado.

Use of nonlinear asymmetrical shock absorber to improve comfort on passenger vehicles

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)