A modification of the matrix iteration using the power method, in conjunction with Hotelling deflation, for the solution of the problem K.x = ω².M.x is here proposed. The problem can be written in the form D.x =λ.x, and the modification consists of raising the matrix D to an appropriate power p before carrying out the iteration process. The selection of a satisfactory value of p is investigated, based on the spacing between the eigenvalues. The effect of p on the accuracy of the results is also discussed. / M.S.

This thesis concerns an active research area within fractal geometry. In the first part, in Chapters 2 and 3, for directed graph iterated function systems (IFSs) defined on ℝ, we prove that a class of 2-vertex directed graph IFSs have attractors that cannot be the attractors of standard (1-vertex directed graph) IFSs, with or without separation conditions. We also calculate their exact Hausdorff measure. Thus we are able to identify a new class of attractors for which the exact Hausdorff measure is known. We give a constructive algorithm for calculating the set of gap lengths of any attractor as a finite union of cosets of finitely generated semigroups of positive real numbers. The generators of these semigroups are contracting similarity ratios of simple cycles in the directed graph. The algorithm works for any IFS defined on ℝ with no limit on the number of vertices in the directed graph, provided a separation condition holds. The second part, in Chapter 4, applies to directed graph IFSs defined on ℝⁿ . We obtain an explicit calculable value for the power law behaviour as r → 0⁺ , of the qth packing moment of μ[subscript(u)], the self-similar measure at a vertex u, for the non-lattice case, with a corresponding limit for the lattice case. We do this (i) for any q ∈ ℝ if the strong separation condition holds, (ii) for q ≥ 0 if the weaker open set condition holds and a specified non-negative matrix associated with the system is irreducible. In the non-lattice case this enables the rate of convergence of the packing L[superscript(q)]-spectrum of μ[subscript(u)] to be determined. We also show, for (ii) but allowing q ∈ ℝ, that the upper multifractal q box-dimension with respect to μ[subscript(u)], of the set consisting of all the intersections of the components of F[subscript(u)], is strictly less than the multifractal q Hausdorff dimension with respect to μ[subscript(u)] of F[subscript(u)].

Siu Chun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 66-68). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Thesis Overview --- p.3 / Chapter 2 --- Background and Related work --- p.4 / Chapter 2.1 --- Emergence of IP-over-ATM --- p.4 / Chapter 2.2 --- ATM architecture --- p.5 / Chapter 2.3 --- Scheduling issues in output-queued switch --- p.6 / Chapter 2.4 --- Scheduling issues in input-queued switch --- p.18 / Chapter 3 --- The Deadline-ordered Burst-based Parallel Scheduling Strategy --- p.23 / Chapter 3.1 --- Introduction --- p.23 / Chapter 3.2 --- Switch and queueing model --- p.24 / Chapter 3.2.1 --- Switch model --- p.24 / Chapter 3.2.2 --- Queueing model --- p.25 / Chapter 3.3 --- The DBPS Strategy --- p.26 / Chapter 3.3.1 --- Motivation --- p.26 / Chapter 3.3.2 --- Strategy --- p.31 / Chapter 3.4 --- The Deadline-ordered Burst-based Parallel Iterative Matching --- p.33 / Chapter 3.4.1 --- Algorithm --- p.34 / Chapter 3.4.2 --- An example of DBPIM --- p.35 / Chapter 3.5 --- Simulation results --- p.33 / Chapter 3.6 --- Discussions --- p.46 / Chapter 3.7 --- Future work --- p.47 / Chapter 4 --- The Quasi-static DBPIM Algorithm --- p.50 / Chapter 4.1 --- Introduction --- p.50 / Chapter 4.2 --- Quasi-static path scheduling principle --- p.51 / Chapter 4.3 --- Quasi-static DBPIM algorithm --- p.56 / Chapter 4.4 --- An example of Quasi-static DBPIM --- p.59 / Chapter 5 --- Conclusion --- p.63 / Bibliography --- p.65

The objective of this research work is to develop reliable and power-efficient synchronization algorithms for continuous phase modulation (CPM). CPM is a bandwidth and power efficient signaling scheme suitable for wireless and mobile communications. Binary CPM schemes have been widely used in many commercial and military systems. CPM with multilevel symbol inputs, i.e., M-ary CPM, can achieve a higher data rate than binary CPM. However, the use of M-ary CPM has been limited due to receiver complexity and synchronization problems. In the last decade, serially concatenated CPM (SCCPM) has drawn more attention since this turbo-like coded scheme can achieve near Shannon-limit performance by performing iterative demodulation/decoding. Note that SCCPM typically operates at a low signal-to-noise ratio, which makes reliable and power-efficient synchronization more challenging. In this thesis, we propose a novel timing and phase recovery technique for CPM. Compared to existing maximum-likelihood estimators, the proposed data-aided synchronizer can achieve a better acquisition performance when a preamble is short or channel model errors are present. We also propose a novel adaptive soft-input soft-output (A-SISO) module for iterative detection with parameter uncertainty. In contrast to the existing A-SISO algorithms using linear prediction, the parameter estimation in the proposed structure is performed in a more general least-squares sense. Based on this scheme, a family of fixed-interval A-SISO algorithms are utilized to implement blind iterative phase synchronization for SCCPM. Moreover, the convergence characteristics of iterative phase synchronization and detection are analyzed by means of density evolution. Particularly, an oscillatory convergence behavior is observed when cycle slips occur during phase tracking. In order to reduce performance degradation due to this convergence fluctuation, design issues, including delay depth of the proposed algorithms, iteration-stopping criteria and interleaver size, are also discussed. Finally, for completeness of the study on phase synchronization, we investigate the error probability performance of noncoherently detected full-response CPM, which does not require channel (or phase) estimation.

Over the last 25 years, interior-point methods (IPMs) have emerged as a viable class of algorithms for solving various forms of conic optimization problems. Most IPMs use a modified Newton method to determine the search direction at each iteration. The system of equations corresponding to the modified Newton system can often be reduced to the so-called normal equation, a system of equations whose matrix ADA' is positive definite, yet often ill-conditioned. In this thesis, we first investigate the theoretical properties of the maximum weight basis (MWB) preconditioner, and show that when applied to a matrix of the form ADA', where D is positive definite and diagonal, the MWB preconditioner yields a preconditioned matrix whose condition number is uniformly bounded by a constant depending only on A. Next, we incorporate the results regarding the MWB preconditioner into infeasible, long-step, primal-dual, path-following algorithms for linear programming (LP) and convex quadratic programming (CQP). In both LP and CQP, we show that the number of iterative solver iterations of the algorithms can be uniformly bounded by n and a condition number of A, while the algorithmic iterations of the IPMs can be polynomially bounded by n and the logarithm of the desired accuracy. We also expand the scope of the LP and CQP algorithms to incorporate a family of preconditioners, of which MWB is a member, to determine an approximate solution to the normal equation. For the remainder of the thesis, we develop a new preconditioning strategy for solving systems of equations whose associated matrix is positive definite but ill-conditioned. Our so-called adaptive preconditioning strategy allows one to change the preconditioner during the course of the conjugate gradient (CG) algorithm by post-multiplying the current preconditioner by a simple matrix, consisting of the identity matrix plus a rank-one update. Our resulting algorithm, the Adaptive Preconditioned CG (APCG) algorithm, is shown to have polynomial convergence properties. Numerical tests are conducted to compare a variant of the APCG algorithm with the CG algorithm on various matrices.

Thesis (M.S.) -- Mississippi State University. Department of Computational Engineering. / Title from title screen. Includes bibliographical references.

CAPES / Este trabalho objetiva apresentar as ideias matemáticas principais da Samambaia de Barnsley, um fractal que recria uma imagem que assemelha-se a uma folha de samambaia da variedade Black Spleenwort e tem como base quatro transformações afins elementares. Algumas mutações da Samambaia de Barnsley são também apresentadas. / This work aims to present the main mathematical ideas of Barnsley’ Fern, a fractal that recreates an image that resembles a fern leaf of the Black Spleenwort variety and is based on four elementary affine transformations. Some mutations of Barnsley’ Fern are also presented.

Orientadores: Sandra Augusta Santos, José Mário Martinez Pérez / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-19T09:49:40Z (GMT). No. of bitstreams: 1 Xavier_LarissaOliveira_D.pdf: 21963947 bytes, checksum: 9419832d56a36ea9d96e9f9d7e75ce57 (MD5) Previous issue date: 2011 / Resumo: Neste trabalho apresentamos o estudo de dois algoritmos baseados em regiões de confiança para minimização de problemas suaves com restrições lineares. O primeiro algoritmo proposto, com uma estratégia de restrições ativas, foi desenvolvido a partir do trabalho de Gay. O segundo algoritmo apresentado explora a técnica de pontos interiores presente nos métodos de barreira. Ambos são acompanhados de respectivos resultados de boa definição e de convergência global e local. Os dois algoritmos foram testados para a resolução de problemas de distribuição de pontos em polígonos, utilizando o algoritmo de Rojas, Santos e Sorensen, livre de fatorações de matrizes, para resolver os subproblemas internos de região de confiança. O problema dos pontos no polígono não foi encontrado na literatura para o teste de algoritmos de otimização e pode ser visto como uma modificação do problema de distribuição de pontos em caixas, sugerido por Powell. Embora possua estrutura favorável para a geração de problemas com dimensão variável, e potencialmente de grande porte, no contexto livre de fatorações, trata-se de um problema difícil e desafiador, com uma grande quantidade de minimizadores locais. Experimentos numéricos comparativos entre as propostas foram feitos e analisados, indicando que os algoritmos são efetivos na obtenção de pontos estacionários de segunda ordem, com ligeira vantagem para o desempenho do algoritmo baseado em restrições ativas, em termos do tempo computacional empregado / Abstract: In this work two trust-region-based algorithms are analyzed for linearly constrained minimization. The first one is an active-set method, based on Gay's ideas. The second one uses interior-point techniques of barrier methods. Both algorithms are proved to be well defined and accompanied by the respective convergence results. The implementation was developed resting upon Rojas, Santos and Sorensen matrix-free algorithm for solving the inner trust-region subproblems. The family of adopted test-problems involves the distribution of points in a polygon, a modification of Powell's problem of distributing points in a square. Despite its favorable structure for generating instances with variable and potentially large dimension, in the matrix-free context, the problem is indeed hard and challenging, with many local minimizers. Comparative computational experiments illustrate the performance of the proposed algorithms, showing that both are effective to obtain second-order stationary points, with a slight advantage of the active-set-based algorithm when it comes to the CPU time spent / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: Márcia Aparecida Gomes Ruggiero, Sandra Augusta Santos / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-21T10:21:10Z (GMT). No. of bitstreams: 1 Begiato_RodolfoGotardi_D.pdf: 3815627 bytes, checksum: 59584610cfd737a94e68dc5bf3735e25 (MD5) Previous issue date: 2012 / Resumo: O objetivo desta tese é tratar da resolução de sistemas não lineares de grande porte, em que as funções são continuamente diferenciáveis, por meio de uma abordagem híbrida que utiliza um método iterativo com duas fases. A primeira fase consiste de versões sem derivadas do método do ponto fixo empregando parâmetros espectrais para determinar o tamanho do passo da direção residual. A segunda fase é constituída pelo método de Newton inexato em uma abordagem matrix-free, em que é acoplado o método GMRES para resolver o sistema linear que determina a nova direção de busca. O método híbrido combina ordenadamente as duas fases de forma que a segunda é acionada somente em caso de falha na primeira e, em ambas, uma condição de decréscimo não-monótono deve ser verificada para aceitação de novos pontos. Desenvolvemos ainda um segundo método, em que uma terceira fase de busca direta é acionada em situações em que o excesso de buscas lineares faz com que o tamanho de passo na direção do método de Newton inexato torne-se demasiadamente pequeno. São estabelecidos os resultados de convergência dos métodos propostos. O desempenho computacional é avaliado em uma série de testes numéricos com problemas tradicionalmente encontrados na literatura. Tanto a análise teórica quanto a numérica evidenciam a viabilidade das abordagens apresentadas neste trabalho / Abstract: This thesis handles large-scale nonlinear systems for which all the involved functions are continuously differentiable. They are solved by means of a hybrid approach based on an iterative method with two phases. The first phase is defined by derivative-free versions of a fixed-point method that employs spectral parameters to define the steplength along the residual direction. The second phase consists of a matrix-free inexact Newton method that employs the GMRES to solve the linear system that computes the search direction. The proposed hybrid method neatly combines the two phases in such a way that the second is called only in case the first one fails. To accept new points in both phases, a nonmonotone decrease condition upon a merit function has to be verified. A second method is developed as well, with a third phase based on direct search, that should act whenever too many line searches have excessively decreased the steplenght along the inexact- Newton direction. Convergence results for the proposed methods are established. The computational performance is assessed in a set of numerical experiments with problems from the literature. Both the theoretical and the experimental analysis corroborate the feasibility of the proposed strategies / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: Christiano Lyra Filho, Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T01:38:37Z (GMT). No. of bitstreams: 1 Casacio_Luciana_D.pdf: 3240577 bytes, checksum: f49bb4444bbbfacf0559d3b88d8feee5 (MD5) Previous issue date: 2015 / Resumo: A solução de problemas de otimização linear através de métodos de pontos interiores envolve a solução de sistemas lineares. Esses sistemas quase sempre possuem dimensões elevadas e alto grau de esparsidade em aplicações reais. Para solução, tipicamente são realizadas operações algébricas que os reduzem a duas formulações mais simples: uma delas, conhecida por "sistema aumentado", envolve matrizes simétricas indefinidas e geralmente esparsas; a outra, denominada "sistema de equações normais", usa matrizes de menor dimensão, simétricas e definidas positivas. A solução dos sistemas lineares é a fase que requer a maior parte do tempo de processamento dos métodos de pontos interiores. Consequentemente, a escolha dos métodos de solução é de extrema importância para que se tenha uma implementação eficiente. Normalmente, aplicam-se métodos diretos para a solução como, por exemplo, a fatoração de Bunch-Parllett ou a fatoração de Cholesky. No entanto, em problemas de grande porte, o uso de métodos diretos torna-se desaconselhável, por limitações de tempo e memória. Nesses casos, abordagens iterativas se tornam mais atraentes. O sucesso da implementação de métodos iterativos depende do uso de bons precondicionadores, pois a matriz de coeficientes torna-se muito mal condicionada, principalmente próximo da solução ótima. Uma alternativa para tratar o problema de mal condicionamento é o uso de abordagens híbridas com duas fases: a fase I utiliza um precondicionador para o sistema de equações normais construído com informações de fatorações incompletas, denominado fatoração controlada de Cholesky; a fase II, utilizada nas últimas iterações, adota o precondicionador separador desenvolvido especificamente para sistemas mal condicionados. O trabalho propõe um novo critério de ordenamento das colunas para construção do precondicionador separador, que preserva a estrutura esparsa da matriz de coeficientes original. Os resultados teóricos desenvolvidos mostram que a matriz precondicionada tem o número de condição limitado quando o ordenamento proposto é adotado. Experimentos computacionais realizados com todos os problemas da biblioteca NETLIB mostram que a abordagem é competitiva com métodos diretos e que o número de condição da matriz precondicionada é muito menor do que o da matriz original. Foram também realizadas comparações com a abordagem híbrida anterior, baseada em precondicionadores que reduzem a esparsidade do sistema de equações. Esses experimentos confirmaram o bom desempenho da metodologia em relação ao número de iterações dos métodos de pontos interiores, aos tempos computacionais e à qualidade das soluções. Esses benefícios foram obtidos com a preservação da esparsidade dos sistemas de equações, o que destaca a adequação da abordagem proposta para a solução de problemas de grande porte / Abstract: The solution of linear optimization problems through interior point methods involves the solution of linear systems. These systems often have high dimensions and high sparsity degree, specially in real applications. Typically algebraic operations are performed to reduce the systems in two simpler formulations: one of them is known as the augmented system, and the other one, referred as normal equation systems, has a smaller dimension matrix which is symmetric positive definite. The solution of linear systems is the interior point methods step that requires most of the processing time. Consequently, the choice of the solution methods are extremely important in order to have an efficient implementation. Usually, direct methods are applied for solving these systems as, for example, Bunch-Parllett factorization or Cholesky factorization. However, in large scale problems, the use of direct methods becomes discouraging by limitations of time and memory. In such cases, iterative approaches are more attractive. The success of iterative method approaches depends on good preconditioners once the coefficient matrix becomes very ill-conditioned, especially close to an optimal solution. An alternative to treat the problem of ill conditioning is to use hybrid approaches with two phases: phase I uses a preconditioner for the normal equation systems built with incomplete factorizations information, called controlled Cholesky factorization; phase II, used in the final iterations, adopts the splitting preconditioner, which was developed specifically for such ill conditioned systems. This work proposes a new ordering criterion for the columns of the splitting preconditioner that preserves the sparse structure of the original coefficient matrix. Theoretical results show that the preconditioned matrix has a limited condition number when the proposed idea is adopted. Computational experiments performed with all NETLIB problems show that the approach is competitive with direct methods and the condition number of the preconditioned matrix is much smaller than the original matrix. Comparisons are also performed with the previous hybrid approach. These experiments confirm the good performance of the methodology. The final number of iterations, processing time and quality of solutions of interior point methods are suitable. These benefits are obtained preserving the sparse structure of the systems, which highlights the suitability of the proposed approach for large scale problems / Doutorado / Automação / Doutora em Engenharia Elétrica