Título: Computation of matrix functions arising in the analysis of complex networks

Michele Benzi
Department of Mathematics and Computer Science
Emory University
Atlanta, GA 30322, USA

Abstract: Quantitative methods of network analysis naturally lead to large-scale computations for functions of matrices associated with sparse graphs. This talk will describe some of the main quantities of interest in network analysis as introduced by Estrada, Hatano, D. Higham and others. We combine decay bounds [2,3] and Gaussian quadrature rules [4] to derive a priori bounds and efficient numerical methods for estimating the quantities of interest. Numerical experiments using small-world, range-free, and Erdos-Renyi graphs will be used to illustrate the effectiveness of the proposed algorithms. This talk is based in part on the paper [1].

This is joint work with Paola Boito (Emory University and CERFACS).

References:

[1] M. Benzi and P. Boito, Quadrature Rule-Based Bounds for Functions of Adjacency Matrices, to appear in Linear Algebra and its Applications.

[2] M. Benzi and G. H. Golub, Bounds for the entries of matrix functions with applications to preconditioning, BIT, 29 (1999), pp. 417-438.

[3] M. Benzi and N. Razouk, Decay bounds and O(n) algorithms for approximating functions of sparse matrices, Electronic Transactions on Numerical Analysis, 28 (2007), pp. 16-39.

[4] G. Meurant and G. H. Golub, Matrices, Moments and Quadrature with Applications. Princeton University Press, Princeton, NJ, 2010.

Título: Parallel Adaptive Cartesian Upwind Methods for Shock-driven Multiphysics Simulation

Ralf Deiterding
Computer Science and Mathematics Division, Oak Ridge National Laboratory
Área: Esquemas numericos adaptativos para PDE (AMR), paralelismo

Abstract: Finite-volume-based shock-capturing methods can most easily be constructed on structured Cartesian meshes. Implementations of higher order discretizations on unstructured grids, on the other hand, can be quite cumbersome. In this talk, an approach in utilizing Cartesian schemes for real-world problems will be presented that combines the ghost-fluid idea with block-structured adaptive mesh refinement. A scalar level set function storing the distance information to the boundary surface is used to consider arbitrary geometries on the Cartesian mesh without ambiguities. Although the boundary incorporation is of first-order accuracy, several examples from compressible gas dynamics will be presented which demonstrate that the utilization of mesh adaptation makes the overall approach suitable for serious computational investigations.

The method has been implemented in the generic fluid solver framework AMROC that is part of the Virtual Test Facility (VTF) software (_http://www.cacr.caltech.edu/asc_). A temporal splitting approach will be described that couples the adaptive Eulerian finite volume method to explicit Lagrangian finite element schemes for computational solid dynamics. Three-dimensional fluid-structure interaction simulations involving large plastic deformations and/or fracture and fragmentation will be shown that confirm the applicability of the proposed techniques to problems with heavily evolving topology. Results obtained with different solid mechanics solvers coupled to AMROC will be compared, and the parallel performance of the fluid solver and the coupled software will be addressed. Essential auxiliary algorithms and software engineering aspects will be discussed. Where they are non-standard, e.g., for gas-liquid flows or detonation waves with detailed chemical kinetics, the employed finite volume schemes and numerical flux functions will be described briefly.

Título:  The generating analytic element approach with application to the modified Helmholtz equation

O. D. L. Strack
University of Minnesota (USA)

Abstract: In this paper a new method for obtaining functions with a given singular behavior that satisfy a class of partial differential equations is presented. Differential equations of this class contain operators of the form !2n, where n is a positive integer. The method uses Wirtinger calculus which enables one to invert the Laplacian in combination with the decomposition method introduced by Adomian at the end of the twentieth century. The procedure uses a singular holomorphic function as its basis, and constructs the solution term by term as an infinite series of functions; the process consists of an infinite number of steps of integration. This method is applied to construct a number of singular solutions to the modified Helmholtz equation in the context of groundwater flow. These functions are discharge potentials, which are two-dimensional functions by definition. The gradient of the discharge potential is the vertically integrated flow over the thickness of an aquifer, or water-bearing layer. The discharge potentials of interest here are those used in the analytic element method. This method, as originally conceived, relies on the superposition of suitably chosen holomorphic functions, and is a form of a method known as the Trefftz method, not to be confused with the Trefftz method applied to finite element techniques. The main analytic elements used are singular line elements, characterized by either a jump along the element In the tangential or the normal component of the discharge vector. The analytic line elements for the case of divergence-free irrotational flow are well established and many of these are forms of singular Cauchy integrals. Application of the analytic element method to more general cases of flow, governed for example by the modified Helmholtz equation (flow in systems of aquifers separated by leaky layers) and the heat equation (transient flow) is possible using the method presented in this paper. The latter application is beyond the scope of this paper, but it is worth noting that for that case the constant that occurs in the modified Helmholtz is replaced by a general function of time and application of Laplace transforms can be avoided. A method for constructing such functions is presented; the procedure for constructing these functions is referred to as the generating analytic element approach. Application of this approach requires the existence of the holomorphic singular line element. The approach is discussed and an example for the case of a line-sink for a system of two aquifers separated by a leaky layer and bounded above by in impermeable boundary is presented.

Keywords Analytic element method · Groundwater flow · Modified Helmholtz equation · Superposition of solutions · Wirtinger calculus

Título: A Neutral Model of Speciation and Diversity

Marcus Aloizio Martinez de Aguiar
Universidade Estadual de Campinas, Instituto de Física Gleb Wataghin, Departamento de Física do Estado Sólido e Ciência dos Materiais.
Área: Sistemas complexos-dinâmica de populações

Abstract: The number of living species on Earth has been estimated to be between 10 and 100 million. Understanding the processes that have generated such remarkable diversity is one of the greatest challenges in evolutionary biology. Speciation is usually related to the isolation of subpopulations by geographic barriers, that stop the genetic flow between the isolated groups, promoting differentiations by mutations and local adaptations that ultimately lead to speciation. In this talk I will dicuss a new mechanism of speciation that does not involve geographical barriers and natural selection. I will present simulations where a population with genetically identical individuals, homogeneously distributed in space, spontaneously breaks up into species when subjected to mutations and to two mating restrictions: individuals can select a mate only from within a maximum spatial distance S from itself and only if the genetic distance between itself and the selected partner is less than a maximum value G. Species develop depending on the mutation rate and on the parameters S and G. The resulting species-area relationships and abundance distributions thus obtained are consistent with observations in nature.

Título: Solving really large sparse linear problems from a range of applications.

Iain Duff
STFC Rutherford Appleton Laboratory, Oxfordshire, UK and CERFACS, Toulouse, France

Abstract: We discuss the solution of large sparse linear systems from a range of application areas mainly from the discretization of three dimensional problems. By large, we mean that the system dimension is of order 10⁷ or more.

We first establish the strength and limitations of direct methods. They are far more powerful than they are often given credit for but, for example, the structure of systems arising from the discretization of partial differential equations from three-dimensional modelling causes particular problems for direct methods inasmuch the factors are much denser than the original system. Moreover, their complexity causes major problems for the convergence of iterative methods and a universally successful preconditioning technique remains to be found.

In this talk we show how direct and iterative methods can be combined to solve problems that are intractable by one class of methods alone. Examples of these hybrid methods include using a direct method as a coarse grid solver in multigrid or to solve subproblems in domain decomposition. We show examples of these approaches and indicate how they can be used to solve very large problems. We also examine hybrid methods that use a fast but potentially inaccurate sparse factorization.

Researchers in the Parallel Algorithms Group at CERFACS in Toulouse have recently solved three-dimensional Helmholtz problems in seismic modelling with over 65 billion unknowns. We briefly discuss how this has been done.

More recently, we have been involved in an RTRA Project on data assimilation called ADTAO which involves the solution of very large sparse nonlinear least-squares problems. We hope to be able to report recent experiments on combining direct and iterative methods in the solution of such problems.

Título: Uma abordagem por otimização linear para a programação do plantio sustentável de vegetais

Marcos Nereu Arenales
ICMC/USP - São Carlos
Área: Otimização combinatória

Resumo: O uso da otimização matemática para o planejamento de plantio de culturas est entre os problemas destacados no artigo pioneiro de Kantorovich (1939) e desde então, muitos outros problemas relacionados têm sido abordados por diferentes técnicas. Nesta palestra são considerados alguns problemas de programação de rotação de culturas sob alguns critérios ecológicos: culturas de mesma família botânica não são plantadas em sequência; culturas para a adubação verde e períodos de pousio devem estar presentes em todas as programações. Um modelo-chave para programação de rotação de culturas é proposto para representar esses critérios ecológicos em adição a restrições técnicas associadas a culturas de vegetais. Alguns problemas de otimização baseados em programação de rotação de culturas são modelados por otimização linear com muitas colunas, as quais são bem determinadas pelo modelo-chave. A técnica de geração de colunas é revisada e aplicada na resolução desses problemas. Experimentos computacionais são discutidos, como também pesquisas futuras.

Título: Zeros de Polinômios e de Funções Inteiras

Dimitar Kolev Dimitrov
IBILCE/UNESP
Área: Teoria da Aproximação

Resumo: O Teorema Fundamental da Álgebra afirma que todo polinômio de grau n possui exatamente n zeros complexos.

O problema de encontrar esses zeros explicitamente vem desafiando os matemáticos desde a época medieval. Surpreendentemente, a maioria das conjecturas e hipóteses importantes na matemática pode ser formulada como problemas sobre caracterização de zeros de certos polinômios e também de classes de polinômios ou de funções que possuem zeros em determinadas regiões do plano complexo.

Um exemplo típico vem da Teoria da Estabilidade, onde o comportamento de soluções de equações diferencias depende da localização dos zeros dos polinômios característicos associados às equações. Discutiremos alguns problemas interessantes sobre zeros de polinômios, suas relações com conjecturas e hipóteses que desafiam matemáticos, e suas aplicações.

Título: re(PER)curso: na busca de um diálogo interdisciplinar entre Modelagem Matemática e Composição Musical

Jônatas Manzolli
Instituto de Artes, Departamento de Música
Núcleo Interdisciplinar de Comunicação Sonora (NICS)
Universidade Estadual de Campinas - UNICAMP

Resumo: A palestra apresenta uma pesquisa que envolve processos criativos musicais e modelagem sonora utilizando-se de recursos matemático-computacionais. Primeiramente, será apresentado um panorama das possibilidades atuais que englobam síntese sonora digital, representação algorítmica de composição e controle de processos interativos de performance musical. O objetivo principal da palestra é divulgar esta abordagem e incentivar outras iniciativas similares. Mas, principalmente, demonstrar que pode-se estabelecer um diálogo entre matemática e música. Trata-se de um entrelaçamento de conhecimento que, desde os tempos remotos da civilização ocidental, cultiva este hábito salutar da "conversa entre amigos". A palestra está relacionada com a performance interativa re(PER)curso apresentada na abertura do XXXIII CNMAC. Nela serão utilizados instrumentos musicais de percussão, gesto corporal e interfaces que através de modelos matemático-computacionais simulam o comportamento de instrumentos acústicos.

Título: INVERSE HEAT TRANSFER PROBLEMS

Helcio R. B. Orlande
Department of Mechanical Engineering
Escola Politécnica/COPPE
Federal University of Rio de Janeiro, UFRJ

Abstract: Systematic methods for the solution of inverse problems have developed significantly during the last twenty years and have become a powerful tool for analysis and design in engineering. Inverse analysis is nowadays a common practice in which the groups involved with experiments and numerical simulation synergistically collaborate throughout the research work, in order to obtain the maximum of information regarding the physical problem under study. Inverse problems are mathematically classified as ill-posed, that is, their solutions do not satisfy either one of the requirements of existence, uniqueness or stability. The solution approaches generally consist of the reformulation of the inverse problem in terms of an approximate well-posed problem. In this paper we briefly review various approaches for the solution of inverse problems, including those based on classical regularization techniques and those based on the Bayesian statistics. Applications of inverse problems are then presented for cases of practical interest, such as the characterization of non-homogeneous materials and the prediction of the temperature Field

Título: High Performance Verified Computing

Walter Krämer
Scientific Computing/Software Engineering
Department of Mathematics and Computer Science
University of Wuppertal Germany

Abstract: We discuss some main points of computer-assisted proofs based on reliable numerical computations. Such so called self-validating or self-verifying numerical methods allow to prove mathematical statements (existence of a fixed point, of a solution of an ODE, of a zero of a continuous function, of a global minimum within a given range, etc.) using a digital computer. To validate the assertions of the underlying mathematical theorems fast finite precision arithmetic is used. The results are absolutely rigorous. We report on the accuracy as well as on the efficiency of the C++ class library C-XSC, our well known open source software tool to facilitate self-verifying numerical calculations. During the last three years the library has been improved significantly with respect to high performance computing within our bilateral Probral project HPVC. As applications we investigate several tasks concerning e.g. dynamical systems as well as concerning the computation of verified functional enclosures for the solutions of some integral equations.

Título: Simulação Numérica de escoamentos com superfícies livres: O trabalho do Grupo do ICMC.

José Alberto Cuminato
ICMC-USP – São Carlos

Resumo: Num trabalho que tornou-se referência obrigatória na área de escoamentos com superfícies livres, Welch, Harlow, Shannon e Daly em 1965, apresentaram um método numérico para solução das equações de Navier-Stokes na presença de superfícies livres. Eles denominaram esse método de MAC (Marker-And-Cell), pois esse método baseia-se na idéia de representação do fluido por partículas marcadoras, que não possuem massa e que são transportadas passivamente pelo fluido. Essas partículas, no entanto, são fundamentais para determinar quais partes do domínio contêm fluido e determinam o domínio de solução das equações de Navier-Stokes. Ao longo dos anos, desde então, muitas outras técnicas surgiram para o tratamento de escoamentos com superfícies livres, e escoamentos multifásicos, tais como o método VOF (Volume Of Fluid) os métodos Level Set, e muitos outros. Todos esses métodos apresentam vantagens e desvantagens. Os métodos do tipo MAC apresentam um bom compromisso entre conservação de massa e tratamento de domínios complexos, mas tem sérios problemas de precisarem de um número muito grande de partículas para representar o fluido, consumindo grandes quantidades de tempo e memória.

Nesta apresentação faremos uma revisão dos trabalhos realizados no ICMC para a simulação de escoamentos com superfícies livres utilizando a metodologia MAC, ressaltando principalmente os últimos desenvolvimentos que permitem a aplicação dessa técnica em muitos problemas reais de escoamentos newtonianos e não-newtonianos. Esses desenvolvimentos são baseados em uma representação eficiente da fronteira utilizando resultados precisos de geometria computacional, para garantir a robustez da estrutura de dados representando o fluido, permitindo a representação, apenas da fronteira da região que contém fluido, em contraste com a representação do domínio completo do método original. Muitos outros aspectos da simulação computacional de escoamentos com superfícies livres serão discutidos em particular a sua utilização na área de Reologia computacional, para a simulação de escoamentos viscoelásticos.

Título: Interação entre multi-espécies na transmissão do Vírus da Febre do Oeste do Nilo

Lourdes Esteva
Faculdade de Ciências, Depto de Matemáticas, UNAM-México

Resumo: A Febre do Oeste do Nilo é uma virose transmitida principalmente por mosquitos do gênero Culex sp. e afeta o sistema nervoso central. As aves são os principais reservatórios do vírus por apresentarem alta viremia por tempo prolongado, constituindo uma fonte de infeção para o vetor. Aves com infecção severa têm taxas altas de morbidade e mortalidade, mas tipicamente desenvolvem imunidade após exposição e uma curta viremia. O homem e demais vertebrados são infectados esporadicamente e não transmitem a doença por apresentarem baixa viremia. No homem, a doença pode ocorrer de forma subclínica ou apresentar sintomas que podem variar desde uma febre passageira a uma encefalite grave. A doença existe endemicamente na África, incluindo Uganda, onde nasce o rio Nilo (daí a origem do nome) e Ásia. Surgiu em 1999 nos EUA, onde já provocou diversas mortes. Acredita-se que o Vírus do Oeste do Nilo é estabelecido como uma epidemia sazonal na América do Norte que irrompe no verão e continua até o outono. Neste trabalho analisa-se a interação entre diferentes espécies de pássaros e mosquitos e sua influência na dinâmica da transmissão do vírus do Oeste do Nilo através de um modelo de equações diferenciais ordinárias. A partir dos diferentes valores para os coeficientes de transmissão entre os mosquitos e os pássaros mede-se o impacto de cada espécie durante os surtos epidêmicos da doença (isto é, a eficiência de cada espécie na transmissão da doença). Em particular, mostra-se que o número reprodutivo básico é dado pela média ponderada do número reprodutivo básico de cada espécie em que os pesos são dados pela abundância relativa da população em cada localidade. Estes resultados sugerem uma possível explicação da ausência de surtos epidêmicos desta infecção no México.