Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size

Let k and l be positive integers. With a graph G, we associate the quantity c(k,l)(G), the number of k-colourings of the edge set of G with no monochromatic matching of size l. Consider the function c(k,l) : N --> N given by c(k,l)(n) = max {c(k,l)(G): vertical bar V(G)vertical bar = n}, the maximum of c(k,l)(G) over all graphs G on n vertices. In this paper, we determine c(k,l)(n) and the corresponding extremal graphs for all large n and all fixed values of k and l.

Sulla progettazione in zona sismica di strutture dotate di dissipatori fluido-viscosi: proposta di una metodologia

CHAPTER 1:FLUID-VISCOUS DAMPERS In this chapter the fluid-viscous dampers are introduced. The first section is focused on the technical characteristics of these devices, their mechanical behavior and the latest evolution of the technology whose they are equipped. In the second section we report the definitions and the guide lines about the design of these devices included in some international codes. In the third section the results of some experimental tests carried out by some authors on the response of these devices to external forces are discussed. On this purpose we report some technical schedules that are usually enclosed to the devices now available on the international market. In the third section we show also some analytic models proposed by various authors, which are able to describe efficiently the physical behavior of the fluid-viscous dampers. In the last section we propose some cases of application of these devices on existing structures and on new-construction structures. We show also some cases in which these devices have been revealed good for aims that lies outside the reduction of seismic actions on the structures. CHAPTER 2:DESIGN METHODS PROPOSED IN LITERATURE In this chapter the more widespread design methods proposed in literature for structures equipped by fluid-viscous dampers are introduced. In the first part the response of sdf systems in the case of harmonic external force is studied, in the last part the response in the case of random external force is discussed. In the first section the equations of motion in the case of an elastic-linear sdf system equipped with a non-linear fluid-viscous damper undergoing a harmonic force are introduced. This differential problem is analytically quite complex and it’s not possible to be solved in a closed form. Therefore some authors have proposed approximate solution methods. The more widespread methods are based on equivalence principles between a non-linear device and an equivalent linear one. Operating in this way it is possible to define an equivalent damping ratio and the problem becomes linear; the solution of the equivalent problem is well-known. In the following section two techniques of linearization, proposed by some authors in literature, are described: the first technique is based on the equivalence of the energy dissipated by the two devices and the second one is based on the equivalence of power consumption. After that we compare these two techniques by studying the response of a sdf system undergoing a harmonic force. By introducing the equivalent damping ratio we can write the equation of motion of the non-linear differential problem in an implicit form, by dividing, as usual, for the mass of the system. In this way, we get a reduction of the number of variables, by introducing the natural frequency of the system. The equation of motion written in this form has two important properties: the response is linear dependent on the amplitude of the external force and the response is dependent on the ratio of the frequency of the external harmonic force and the natural frequency of the system only, and not on their single values. All these considerations, in the last section, are extended to the case of a random external force. CHAPTER 3: DESIGN METHOD PROPOSED In this chapter the theoretical basis of the design method proposed are introduced. The need to propose a new design method for structures equipped with fluid-viscous dampers arises from the observation that the methods reported in literature are always iterative, because the response affects some parameters included in the equation of motion (such as the equivalent damping ratio). In the first section the dimensionless parameterε is introduced. This parameter has been obtained from the definition of equivalent damping ratio. The implicit form of the equation of motion is written by introducing the parameter ε, instead of the equivalent damping ratio. This new implicit equation of motions has not any terms affected by the response, so that once ε is known the response can be evaluated directly. In the second section it is discussed how the parameter ε affects some characteristics of the response: drift, velocity and base shear. All the results described till this point have been obtained by keeping the non-linearity of the behavior of the dampers. In order to get a linear formulation of the problem, that is possible to solve by using the well-known methods of the dynamics of structures, as we did before for the iterative methods by introducing the equivalent damping ratio, it is shown how the equivalent damping ratio can be evaluated from knowing the value of ε. Operating in this way, once the parameter ε is known, it is quite easy to estimate the equivalent damping ratio and to proceed with a classic linear analysis. In the last section it is shown how the parameter ε could be taken as reference for the evaluation of the convenience of using non-linear dampers instead of linear ones on the basis of the type of external force and the characteristics of the system. CHAPTER 4: MULTI-DEGREE OF FREEDOM SYSTEMS In this chapter the design methods of a elastic-linear mdf system equipped with non-linear fluidviscous dampers are introduced. It has already been shown that, in the sdf systems, the response of the structure can be evaluated through the estimation of the equivalent damping ratio (ξsd) assuming the behavior of the structure elastic-linear. We would to mention that some adjusting coefficients, to be applied to the equivalent damping ratio in order to consider the actual behavior of the structure (that is non-linear), have already been proposed in literature; such coefficients are usually expressed in terms of ductility, but their treatment is over the aims of this thesis and we does not go into further. The method usually proposed in literature is based on energy equivalence: even though this procedure has solid theoretical basis, it must necessary include some iterative process, because the expression of the equivalent damping ratio contains a term of the response. This procedure has been introduced primarily by Ramirez, Constantinou et al. in 2000. This procedure is reported in the first section and it is defined “Iterative Method”. Following the guide lines about sdf systems reported in the previous chapters, it is introduced a procedure for the assessment of the parameter ε in the case of mdf systems. Operating in this way the evaluation of the equivalent damping ratio (ξsd) can be done directly without implementing iterative processes. This procedure is defined “Direct Method” and it is reported in the second section. In the third section the two methods are analyzed by studying 4 cases of two moment-resisting steel frames undergoing real accelerogramms: the response of the system calculated by using the two methods is compared with the numerical response obtained from the software called SAP2000-NL, CSI product. In the last section a procedure to create spectra of the equivalent damping ratio, affected by the parameter ε and the natural period of the system for a fixed value of exponent α, starting from the elasticresponse spectra provided by any international code, is introduced.

Entwicklung und Tests von Algorithmen für die Impedanztomographie

Die Elektrische Impedanztomographie soll als kostengünstige und nebenwirkungsfreie Tomographiemethode in der medizinischen Diagnostik, z. B. in der Mammographie dienen. Mit der EIT läßt sich Krebsgewebe von gesundem Gewebe unterscheiden, da es eine signifikant erhöhte Leitfähigkeit aufweist. Damit kann die EIT als Ergänzung zu den klassischen Diagnoseverfahren dienen. So ist z.B. bei jungen Frauen mit einem dichteren Fettgewebe die Identifizierung eines Mammakarzinoms mit der Röntgentomographie nicht immer möglich. Ziel dieser Arbeit war es, einen Prototypen für die Impedanztomographie zu entwickeln und mögliche Anwendungen zu testen. Der Tomograph ist in Zusammenarbeit mit Dr. K.H.Georgi gebaut worden. Der Tomograph erlaubt es niederohmige, Wechselströme an Elektroden auf der Körperoberfläche einzuspeisen. Die Potentiale können an diesen Elektroden programmierbar vorgegeben werden. Weitere hochohmige Elektroden dienen zur Potentialmessung. Um den Hautwiderstand zu überbrücken, werden Wechselstromfrequenzen von 20-100 kHz eingesetzt. Mit der Möglichkeit der Messung von Strom und Potential auf unterschiedlichen Elektroden kann man das Problem des nur ungenau bekannten Hautwiderstandes umgehen. Prinzipiell ist es mit dem Mainzer EIT System möglich, 100 Messungen in der Sekunde durchzuführen. Auf der Basis von mit dem Mainzer EIT gewonnenen Daten sollten unterschiedliche Rekonstruktionsalgorithmen getestet und weiterentwickelt werden. In der Vergangenheit sind verschiedene Rekonstruktionsalgorithmen für das mathematisch schlecht gestellte EIT Problem betrachtet worden. Sie beruhen im Wesentlichen auf zwei Strategien: Die Linearisierung und iterative Lösung des Problems und Gebietserkennungsmethoden. Die iterativen Verfahren wurden von mir dahingehend modifiziert, dass Leitfähigkeitserhöhungen und Leitfähigkeitserniedrigungen gleichberechtigt behandelt werden können. Für den modifizierten Algorithmus wurden zwei verschiedene Rekonstruktionsalgorithmen programmiert und mit synthetischen Daten getestet. Zum einen die Rekonstruktion über die approximative Inverse, zum anderen eine Rekonstruktion mit einer Diskretisierung. Speziell für die Rekonstruktion mittels Diskretisierung wurde eine Methode entwickelt, mit der zusätzliche Informationen in der Rekonstruktion berücksichtigt werden können, was zu einer Verbesserung der Rekonstruktion beiträgt. Der Gebietserkennungsalgorithmus kann diese Zusatzinformationen liefern. In der Arbeit wurde ein neueres Verfahren für die Gebietserkennung derart modifiziert, dass eine Rekonstruktion auch für getrennte Strom- und Spannungselektroden möglich wurde. Mit Hilfe von Differenzdaten lassen sich ausgezeichnete Rekonstruktionen erzielen. Für die medizinischen Anwendungen sind aber Absolutmessungen nötig, d.h. ohne Leermessung. Der erwartende Effekt einer Inhomogenität in der Leitfähigkeit ist sehr klein und als Differenz zweier grosser Zahlen sehr schwierig zu bestimmen. Die entwickelten Algorithmen kommen auch gut mit Absolutdaten zurecht.

Spectral estimates and preconditioning for saddle point systems arising from optimization problems

In this thesis, we consider the problem of solving large and sparse linear systems of saddle point type stemming from optimization problems. The focus of the thesis is on iterative methods, and new preconditioning srategies are proposed, along with novel spectral estimtates for the matrices involved.

Automated optimization of polymer extrusion dies using finite element analysis

An extrusion die is used to continuously produce parts with a constant cross section; such as sheets, pipes, tire components and more complex shapes such as window seals. The die is fed by a screw extruder when polymers are used. The extruder melts, mixes and pressures the material by the rotation of either a single or double screw. The polymer can then be continuously forced through the die producing a long part in the shape of the die outlet. The extruded section is then cut to the desired length. Generally, the primary target of a well designed die is to produce a uniform outlet velocity without excessively raising the pressure required to extrude the polymer through the die. Other properties such as temperature uniformity and residence time are also important but are not directly considered in this work. Designing dies for optimal outlet velocity variation using simple analytical equations are feasible for basic die geometries or simple channels. Due to the complexity of die geometry and of polymer material properties design of complex dies by analytical methods is difficult. For complex dies iterative methods must be used to optimize dies. An automated iterative method is desired for die optimization. To automate the design and optimization of an extrusion die two issues must be dealt with. The first is how to generate a new mesh for each iteration. In this work, this is approached by modifying a Parasolid file that describes a CAD part. This file is then used in a commercial meshing software. Skewing the initial mesh to produce a new geometry was also employed as a second option. The second issue is an optimization problem with the presence of noise stemming from variations in the mesh and cumulative truncation errors. In this work a simplex method and a modified trust region method were employed for automated optimization of die geometries. For the trust region a discreet derivative and a BFGS Hessian approximation were used. To deal with the noise in the function the trust region method was modified to automatically adjust the discreet derivative step size and the trust region based on changes in noise and function contour. Generally uniformity of velocity at exit of the extrusion die can be improved by increasing resistance across the die but this is limited by the pressure capabilities of the extruder. In optimization, a penalty factor that increases exponentially from the pressure limit is applied. This penalty can be applied in two different ways; the first only to the designs which exceed the pressure limit, the second to both designs above and below the pressure limit. Both of these methods were tested and compared in this work.

Efficient Model-based 3D Tracking by Using Direct Image Registration

This thesis deals with the problem of efficiently tracking 3D objects in sequences of images. We tackle the efficient 3D tracking problem by using direct image registration. This problem is posed as an iterative optimization procedure that minimizes a brightness error norm. We review the most popular iterative methods for image registration in the literature, turning our attention to those algorithms that use efficient optimization techniques. Two forms of efficient registration algorithms are investigated. The first type comprises the additive registration algorithms: these algorithms incrementally compute the motion parameters by linearly approximating the brightness error function. We centre our attention on Hager and Belhumeur’s factorization-based algorithm for image registration. We propose a fundamental requirement that factorization-based algorithms must satisfy to guarantee good convergence, and introduce a systematic procedure that automatically computes the factorization. Finally, we also bring out two warp functions to register rigid and nonrigid 3D targets that satisfy the requirement. The second type comprises the compositional registration algorithms, where the brightness function error is written by using function composition. We study the current approaches to compositional image alignment, and we emphasize the importance of the Inverse Compositional method, which is known to be the most efficient image registration algorithm. We introduce a new algorithm, the Efficient Forward Compositional image registration: this algorithm avoids the necessity of inverting the warping function, and provides a new interpretation of the working mechanisms of the inverse compositional alignment. By using this information, we propose two fundamental requirements that guarantee the convergence of compositional image registration methods. Finally, we support our claims by using extensive experimental testing with synthetic and real-world data. We propose a distinction between image registration and tracking when using efficient algorithms. We show that, depending whether the fundamental requirements are hold, some efficient algorithms are eligible for image registration but not for tracking.

Combining a Similar Coefficient Identification Algorithm with the Boundary Element Method

The boundary element method (BEM) has been applied successfully to many engineering problems during the last decades. Compared with domain type methods like the finite element method (FEM) or the finite difference method (FDM) the BEM can handle problems where the medium extends to infinity much easier than domain type methods as there is no need to develop special boundary conditions (quiet or absorbing boundaries) or infinite elements at the boundaries introduced to limit the domain studied. The determination of the dynamic stiffness of arbitrarily shaped footings is just one of these fields where the BEM has been the method of choice, especially in the 1980s. With the continuous development of computer technology and the available hardware equipment the size of the problems under study grew and, as the flop count for solving the resulting linear system of equations grows with the third power of the number of equations, there was a need for the development of iterative methods with better performance. In [1] the GMRES algorithm was presented which is now widely used for implementations of the collocation BEM. While the FEM results in sparsely populated coefficient matrices, the BEM leads, in general, to fully or densely populated ones, depending on the number of subregions, posing a serious memory problem even for todays computers. If the geometry of the problem permits the surface of the domain to be meshed with equally shaped elements a lot of the resulting coefficients will be calculated and stored repeatedly. The present paper shows how these unnecessary operations can be avoided reducing the calculation time as well as the storage requirement. To this end a similar coefficient identification algorithm (SCIA), has been developed and implemented in a program written in Fortran 90. The vertical dynamic stiffness of a single pile in layered soil has been chosen to test the performance of the implementation. The results obtained with the 3-d model may be compared with those obtained with an axisymmetric formulation which are considered to be the reference values as the mesh quality is much better. The entire 3D model comprises more than 35000 dofs being a soil region with 21168 dofs the biggest single region. Note that the memory necessary to store all coefficients of this single region is about 6.8 GB, an amount which is usually not available with personal computers. In the problem under study the interface zone between the two adjacent soil regions as well as the surface of the top layer may be meshed with equally sized elements. In this case the application of the SCIA leads to an important reduction in memory requirements. The maximum memory used during the calculation has been reduced to 1.2 GB. The application of the SCIA thus permits problems to be solved on personal computers which otherwise would require much more powerful hardware.

Método multigrid algébrico: reutilização das estruturas multigrid no transporte de contaminantes

A necessidade de obter solução de grandes sistemas lineares resultantes de processos de discretização de equações diferenciais parciais provenientes da modelagem de diferentes fenômenos físicos conduz à busca de técnicas numéricas escaláveis. Métodos multigrid são classificados como algoritmos escaláveis.Um estimador de erros deve estar associado à solução numérica do problema discreto de modo a propiciar a adequada avaliação da solução obtida pelo processo de aproximação. Nesse contexto, a presente tese caracteriza-se pela proposta de reutilização das estruturas matriciais hierárquicas de operadores de transferência e restrição dos métodos multigrid algébricos para acelerar o tempo de solução dos sistemas lineares associados à equação do transporte de contaminantes em meio poroso saturado. Adicionalmente, caracteriza-se pela implementação das estimativas residuais para os problemas que envolvem dados constantes ou não constantes, os regimes de pequena ou grande advecção e pela proposta de utilização das estimativas residuais associadas ao termo de fonte e à condição inicial para construir procedimentos adaptativos para os dados do problema. O desenvolvimento dos códigos do método de elementos finitos, do estimador residual e dos procedimentos adaptativos foram baseados no projeto FEniCS, utilizando a linguagem de programação PYTHONR e desenvolvidos na plataforma Eclipse. A implementação dos métodos multigrid algébricos com reutilização considera a biblioteca PyAMG. Baseado na reutilização das estruturas hierárquicas, os métodos multigrid com reutilização com parâmetro fixo e automática são propostos, e esses conceitos são estendidos para os métodos iterativos não-estacionários tais como GMRES e BICGSTAB. Os resultados numéricos mostraram que o estimador residual captura o comportamento do erro real da solução numérica, e fornece algoritmos adaptativos para os dados cuja malha retornada produz uma solução numérica similar à uma malha uniforme com mais elementos. Adicionalmente, os métodos com reutilização são mais rápidos que os métodos que não empregam o processo de reutilização de estruturas. Além disso, a eficiência dos métodos com reutilização também pode ser observada na solução do problema auxiliar, o qual é necessário para obtenção das estimativas residuais para o regime de grande advecção. Esses resultados englobam tanto os métodos multigrid algébricos do tipo SA quanto os métodos pré-condicionados por métodos multigrid algébrico SA, e envolvem o transporte de contaminantes em regime de pequena e grande advecção, malhas estruturadas e não estruturadas, problemas bidimensionais, problemas tridimensionais e domínios com diferentes escalas.

Método de estimativa de torque da articulação do joelho baseada em EMG

Este trabalho apresenta um método de estimativa de torque do joelho baseado em sinais eletromiográficos (EMG) durante terapia de reabilitação robótica. Os EMGs, adquiridos de cinco músculos envolvidos no movimento de flexão e extensão do joelho, são processados para encontrar as ativações musculares. Em seguida, mediante um modelo simples de contração muscular, são calculadas as forças e, usando a geometria da articulação, o torque do joelho. As funções de ativação e contração musculares possuem parâmetros limitados que devem ser calibrados para cada usuário, sendo o ajuste feito mediante a minimização do erro entre o torque estimado e o torque medido na articulação usando a dinâmica inversa. São comparados dois métodos iterativos para funções não-lineares como técnicas de otimização restrita para a calibração dos parâmetros: Gradiente Descendente e Quasi-Newton. O processamento de sinais, calibração de parâmetros e cálculo de torque estimado foram desenvolvidos no software MATLAB®; o cálculo de torque medido foi feito no software OpenSim com sua ferramenta de dinâmica inversa.

A factorization procedure that is equivalent to successive over relaxation /

"This work was supported in part by the National Science Foundation under Grant No. GJ812."

Recent developments in the quantum dynamical characterization of unimolecular resonances

We give a selective review of quantum mechanical methods for calculating and characterizing resonances in small molecular systems, with an emphasis on recent progress in Chebyshev and Lanczos iterative methods. Two archetypal molecular systems are discussed: isolated resonances in HCO, which exhibit regular mode and state specificity, and overlapping resonances in strongly bound HO2, which exhibit irregular and chaotic behavior. Recent progresses for non-zero total angular momentum J calculations of resonances including parallel computing models are also included and future directions in this field are discussed.

Comment on "Grover search with pairs of trapped ions"

In this Comment on Feng's paper [Phys. Rev. A 63, 052308 (2001)], we show that Grover's algorithm may be performed exactly using the gate set given, provided that small changes are made to the gate sequence. An analytic expression for the probability of success of Grover's algorithm for any unitary operator U instead of Hadamard gate is presented.

Oscillatory regulation of hes1: Discrete stochastic delay modelling and simulation

Discrete stochastic simulations are a powerful tool for understanding the dynamics of chemical kinetics when there are small-to-moderate numbers of certain molecular species. In this paper we introduce delays into the stochastic simulation algorithm, thus mimicking delays associated with transcription and translation. We then show that this process may well explain more faithfully than continuous deterministic models the observed sustained oscillations in expression levels of hes1 mRNA and Hes1 protein.

A flaw in the use of minimal defining sets for secret sharing schemes

It is shown that in some cases it is possible to reconstruct a block design D uniquely from incomplete knowledge of a minimal defining set for D. This surprising result has implications for the use of minimal defining sets in secret sharing schemes.