Research Reports

4/2002 Computational Comparison of Alternative Strategies with Interior Point Methods for Network Piecewise Linear Programs
Fernando A. S. Marins, Clovis Perin, Margarida P. Mello

The usual approach to solving a piecewise linear network flow problem is to transform it into an equivalent linear one. In this transformation, a piecewise network with n nodes and m arcs, each with intervals to each linear piece of the cost function associated to arc j, has an equivalent linear one with n nodes and = arcs. Interior point methods have been proved successful in the solution of linear network flow problems. We show that is advantageous to construct a customized interior point method to solve piecewise linear network problems directly, instead of applying its generic version to the equivalent linear problem. Two algorithms were implemented and tested: one using predictor-corrector and the other without the corrector step. Comparison between alternative strategies (initialization and stopping criteria) is done by means of several computational tests.


PDF icon rp-2002-4.pdf
3/2002 Invariant Control Sets on Flag Manifolds and Ideal Boundary
Marcelo Firer, Osvaldo G. Rocio

Let $G$ be a semisimple real Lie group of non-compact type, $K$ a maximal compact subgroup and $S\subseteq G$ a semigroup with nonempty interior. We consider the ideal boundary $\partial_{\infty }\left( G/K\right) $ of the associated symmetric space and the flag manifolds $G/P_{\Theta }$. We prove that the asymptotic image $\partial _{\infty }\left( Sx_{0}\right) \subseteq \partial _{\infty }\left( G/K\right) $, where $x_{0}\in G/K$ is any given point, is the maximal invariant control set of $S$ in $\partial_{\infty }\left( G/K\right) $. Moreover there is a surjective projection $\pi :\partial _{\infty }\left( Sx_{0}\right) \rightarrow \bigcup\limits_{\Theta \subseteq \Sigma }C_{\Theta }$, where $C_{\Theta }$ is the maximal invariant control set for the action of $S$ in the flag manifold $G/P_{\Theta }$, with $P_{\Theta }$ a parabolic subgroup. The points that project over $C_{\Theta } $ are exactly the points of type $\Theta $ in $\partial _{\infty }\left( Sx_{0}\right) $ (in the sense of the type of a cell in a Tits Building).


PDF icon rp-2002-3.pdf
2/2002 Graded identities for the algebra of $n\times n$ upper triangular matrices over an infinite field
Plamen Koshlukov, Angela Valenti

We consider the algebra $U_n(K)$ of $n\times n$ upper triangular matrices over an infinite field $K$ equipped with its usual $\mathbb{Z}_n$-grading. We describe a basis of the ideal of the graded polynomial identities for this algebra, and compute some of the numerical invariants of this ideal. An extended version of this research will be published elsewhere.


PDF icon rp-2002-2.pdf
1/2002 An Inverse Two-Columns Updating Method for solving large-scale nonlinear systems of equations
Véra L. R. Lopes, Luziane Ferreira-Mendonça, Rosana Pérez

In this work it is introduced a new quasi-Newton method for solving large-scale nonlinear systems of equations. In this method two columns of the approximation of the inverse Jacobian are updated, in such a way that the two last secant equations are satisfied (when it is possible) at every iteration. The new method is called the Inverse Two-Columns Updating Method (ITCUM). Moreover, it is proposed a right implementation from the point of view of linear algebra and numerical stability. It is presented a local convergence analysis and several numerical tests an a comparison between the performance of this new quasi-Newton method with other quasi-Newton methods, in particular the ICUM (Inverse Column Updating Method) \cite{zam}.


PDF icon rp-2002-1.pdf
48/2001 Multiparametric traveltime inversions
Ricardo Biloti, Lúcio T. Santos, Martin Tygel

In conventional seismic processing, the classical algorithm of Hubral and Krey is routinely applied to extract na initial macrovelocity model that consists of a stack of homogeneous layers bounded by curved interfaces. Input for the algorithm are derived from a previous velocity analysis conducted on common midpoint (CMP) data. This work presents a modified version of the Hubral and Krey algorithm that is designed to extend the original version in two ways, namely (a) it makes na advantageous use of previously obtained common reflection surface (CRS) attributes as its input, and (b) it also allows for gradient layer velocity in depth. A new strategy to recover interfaces as optimized cubic splines is also proposed. Some synthetic examples are provided to illustrate and explain the implementations of the method.


PDF icon rp-2001-48.pdf
47/2001 Topographic effect correction using CRS parameters
Valeria Grosfeld, Ricardo Biloti, Lúcio T. Santos, Martin Tygel

The Common Reflection Surface (CRS) is a stacking process that simulates a zero-offset section and provides useful parameters sections. It can be applied to the real non horizontal measurement surface and it is necessary to remove the topographic effect to obtain a more accurate section to be interpretated. This work presents a new technique to remove the topographic effect: continuation of the information to a chosen depth datum using the CRS parameter. A synthetic example is provided to illustrate the approach.


PDF icon rp-2001-47.pdf
46/2001 Lyapunov graph continuation
Maria Alice Bertolim, Margarida P. Mello, Ketty A. de Rezende

In this paper the Poincaré-Hopf inequalities are shown to be necessary and sufficient conditions for an abstract Lyapunov graph L to be continued to an abstract Lyapunov graph of Morse type. The Lyapunov graph considered represents smooth flows on closed orientable n-manifolds, n>2. The continuation which is presented by means of a constructive algorithm, is shown to be unique in dimensions two and three. In all other dimensions, upper bounds on the number of possible continuations of L are presented.


PDF icon rp-2001-46.pdf
45/2001 Weak solutions of a phase-field model with convection for solidification of an alloy
Gabriela Planas, José Luiz Boldrini

In recent years, the phase-field methodology has achieved considerable importance in modeling and numerically simulating a range of phase transitions and complex growth structures that occur during solidification processes. In attempt to understand the mathematical aspects of such methodology, in this article we consider a simplified model of this sort for a nonstationary process of solidification/melting of a binary alloy with thermal properties. The model includes the possibility of occurrence of natural convection in non-solidified regions and, therefore, leads to a free-boundary value problem for a highly non-linear system of partial differential equations consisting of a phase-field equation, a heat equation, a concentration equation and a modified Navier-Stokes equations by a penalization term of Carman-Kozeny type, which accounts for the mushy effects, and Boussinesq terms to take in consideration the effects of variations of temperature and concentration in the flow.A proof of existence of weak solutions for the system is given. The problem is firstly approximated and a sequence of approximate solutions is obtained by Leray-Schauder's fixed point theorem. A solution of the original problem is then found by using compactness arguments.


PDF icon rp-2001-45.pdf
44/2001 Solving recent applications by quasi-Newton methods
Rosana Pérez, Véra L. R. Lopes

In \cite{ros}, we have shown that there are many recent problems in applied research for which the quasi-Newton methods are the best option for solving the nonlinear systems of equations that appear in the solution of such problems. The main reason for using these methods is because they have low computational cost \cite{mar}, \cite{lop1}, \cite{lop}. Motivated by this work and by the fact that the ICUM, was considered recently as the most efficient quasi-Newton method for solving large-scale nonlinear systems \cite{luksan}, we are now interested in implementing it with some real problems.For this, we consider in this work four problems of common occurrence in applications in Geophysics, Biology, Engineering and Physics, respectively. Two of them are described here based in recent works \cite{carlos},\cite{sil}. The two other applications were described in \cite{ros} with base in \cite{med},\cite{mil}.For solving each problem, we must solve a nonlinear system of equations. For this, we use the quasi-Newton methods: Broyden and ICUM and present a careful comparative analysis of the results obtained.


PDF icon rp-2001-44.pdf
43/2001 Fuzzy Quasilinear Spaces
Yurilev Chalco-Cano, Marko A. Rojas-Medar, Adilson J. Vieira-Brandão

We introduce the concept of fuzzy quasilinear space and fuzzy quasilinear operator. Moreover we state some properties and give results which extend to the fuzzy context some results of linear functional analysis.


PDF icon rp-2001-43.pdf