Dissertations / Theses on the topic 'Tridiagonal matrices'

Première partie: la convergence globale de l'algorithme QR avec le shift de Rayleigh appliquée à une matrice normale Hessenberg supérieure irréductible est démontrée. Ensuite nous avons proposé un shift avec lequel la convergence est cubique, lorsque la matrice est symétrique tridiagonale irréductible. Deuxième partie: nous avons proposé une méthode pour le calcul d'une valeur propre de rang donné d'une matrice symétrique tridiagonale irréductible, cette méthode est un procédé d'initialisation de la méthode dite d'itération inverse de Rayleigh

Nous nous intéressons dans cette thèse, à l'étude de certaines méthodes numériques de type krylov dans le cas symplectique, en utilisant la technique de blocs. Ces méthodes, contrairement aux méthodes classiques, permettent à la matrice réduite de conserver la structure Hamiltonienne ou anti-Hamiltonienne ou encore symplectique d'une matrice donnée. Parmi ces méthodes, nous nous sommes intéressés à la méthodes d'Arnoldi symplectique par bloc que nous appelons aussi bloc J-Arnoldi. Notre but essentiel est d’étudier cette méthode de façon théorique et numérique, sur la nouvelle structure du K-module libre ℝ²nx²s avec K = ℝ²sx²s où s ≪ n désigne la taille des blocs utilisés. Un deuxième objectif est de chercher une approximation de l'epérateur exp(A)V, nous étudions en particulier le cas où A est une matrice réelle Hamiltonnienne et anti-symétrique de taille 2n x 2n et V est une matrice rectangulaire ortho-symplectique de taille 2n x 2s sur le sous-espace de Krylov par blocs Km(A,V) = blockspan {V,AV,...,Am-1V}, en conservant la structure de la matrice V. Cette approximation permet de résoudre plusieurs problèmes issus des équations différentielles dépendants d'un paramètre (EDP) et des systèmes d'équations différentielles ordinaires (EDO). Nous présentons également une méthode de Lanczos symplectique par bloc, que nous nommons bloc J-Lanczos. Cette méthode permet de réduire une matrice structurée sous la forme J-tridiagonale par bloc. Nous proposons des algorithmes basés sur deux types de normalisation : la factorisation S R et la factorisation Rj R. Dans une dernière partie, nous proposons un algorithme qui généralise la méthode de Greville afin de déterminer la pseudo inverse de Moore-Penros bloc de lignes par bloc de lignes d'une matrice rectangulaire de manière itérative. Nous proposons un algorithme qui utilise la technique de bloc. Pour toutes ces méthodes, nous proposons des exemples numériques qui montrent l'efficacité de nos approches
We study, in this thesis, some numerical block Krylov subspace methods. These methods preserve geometric properties of the reduced matrix (Hamiltonian or skew-Hamiltonian or symplectic). Among these methods, we interest on block symplectic Arnoldi, namely block J-Arnoldi algorithm. Our main goal is to study this method, theoretically and numerically, on using ℝ²nx²s as free module on (ℝ²sx²s, +, x) with s ≪ n the size of block. A second aim is to study the approximation of exp (A)V, where A is a real Hamiltonian and skew-symmetric matrix of size 2n x 2n and V a rectangular matrix of size 2n x 2s on block Krylov subspace Km (A, V) = blockspan {V, AV,...Am-1V}, that preserve the structure of the initial matrix. this approximation is required in many applications. For example, this approximation is important for solving systems of ordinary differential equations (ODEs) or time-dependant partial differential equations (PDEs). We also present a block symplectic structure preserving Lanczos method, namely block J-Lanczos algorithm. Our approach is based on a block J-tridiagonalization procedure of a structured matrix. We propose algorithms based on two normalization methods : the SR factorization and the Rj R factorization. In the last part, we proposea generalized algorithm of Greville method for iteratively computing the Moore-Penrose inverse of a rectangular real matrix. our purpose is to give a block version of Greville's method. All methods are completed by many numerical examples

Nous analysons le spectre d'une matrice defini par un hamiltonien h a (1+2) corps, agissant dans un espace de n particules. D'abord, il est demontre que la densite de niveaux est donnee par une fonction binomiale continue determinee par les trois premiers moments de h et par la dimension de l'espace. Les seules deviations apparaissent sur la position de l'etat fondamental du systeme. Pour le localiser, la theorie est reformulee en termes de l'algorithme de lanczos, dans lequel la base est definie en agissant de facon repetee sur un vecteur initial (|0>) et en orthogonalisant a chaque etape, ce qui nous conduit a la forme tridiagonale de la matrice. Il a ete demontre qu'avec un choix judicieux de |0>, les quelques premiers moments <0|h k|> sont suffisants pour determiner de facon precise l'energie de l'etat fondamental. Nous demontrons aussi que les elements de matrice (au dela des premiers n = o(n)) ont une forme generale-binomiale inverse pour les non-diagonaux, logarithme pour les diagonaux-entierement determinee par les memes quatre parametres definissant la densite de niveaux globale. Ces resultats sont utilises pour estimer la densite de niveaux en termes des fonctions de structure gamow teller experimentales.

Dissertação (mestrado)–Universidade de Brasília, Universidade UnB de Planaltina, Programa de Pós-Graduação em Ciência de Materiais, 2015.
Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2015-12-15T17:59:17Z No. of bitstreams: 1 2015_LindomarJoséRocha.pdf: 1300687 bytes, checksum: f028dc5aba5d9f92f1b2ee949e3e3a3d (MD5)
Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-02-29T22:14:44Z (GMT) No. of bitstreams: 1 2015_LindomarJoséRocha.pdf: 1300687 bytes, checksum: f028dc5aba5d9f92f1b2ee949e3e3a3d (MD5)
Made available in DSpace on 2016-02-29T22:14:44Z (GMT). No. of bitstreams: 1 2015_LindomarJoséRocha.pdf: 1300687 bytes, checksum: f028dc5aba5d9f92f1b2ee949e3e3a3d (MD5)
Diversos ramos do conhecimento humano fazem uso de autovalores e autovetores, dentre eles têm-se Física, Engenharia, Economia, etc. A determinação desses autovalores e autovetores pode ser feita utilizando diversas rotinas computacionais, porém umas mais rápidas que outras nesse senário de ganho de velocidade aparece a opção de se usar a computação paralela de forma mais especifica a CUDA da Nvidia é uma opção que oferece um ganho de velocidade significativo, nesse modelo as rotinas são executadas na GPU onde se tem diversos núcleos de processamento. Dada a tamanha importância dos autovalores e autovetores o objetivo desse trabalho é determinar rotinas que possam efetuar o cálculos dos mesmos com matrizes tridiagonais simétricas reais de maneira mais rápida e segura, através de computação paralela com uso da CUDA. Objetivo esse alcançado através da combinação de alguns métodos numéricos para a obtenção dos autovalores e um alteração no método da iteração inversa utilizado na determinação dos autovetores. Temos feito uso de rotinas LAPACK para comparar com as nossas rotinas desenvolvidas em CUDA. De acordo com os resultados, a rotina desenvolvida em CUDA tem a vantagem clara de velocidade quer na precisão simples ou dupla, quando comparado com o estado da arte das rotinas de CPU a partir da biblioteca LAPACK. ______________________________________________________________________________________________ ABSTRACT
Severa branches of human knowledge make use of eigenvalues and eigenvectors, among them we have physics, engineering, economics, etc. The determination of these eigenvalues and eigenvectors can be using various computational routines, som faster than others in this speed increase scenario appears the option to use the parallel computing more specifically the Nvidia’s CUDA is an option that provides a gain of significant speed, this model the routines are performed on the GPU which has several processing cores. Given the great importance of the eigenvalues and eigenvectors the objective of this study is to determine routines that can perform the same calculations with real symmetric tridiagonal matrices more quickly and safely, through parallel computing with use of CUDA. Objective that achieved by some combination of numerical methods to obtain the eigenvalues and a change in the method of inverse iteration used to determine of the eigenvectors, which was used LAPACK routines to compare with routine developed in CUDA. According to the results of the routine developed in CUDA has marked superiority with single or double precision, in the question speed regarding the routines of LAPACK.

Dissertação (mestrado)–Universidade de Brasília, Universidade UnB de Planaltina, Programa de Pós-Graduação em Ciência de Materiais, 2015.
Submitted by Raquel Viana (raquelviana@bce.unb.br) on 2016-06-01T21:17:59Z No. of bitstreams: 1 2015_WilsonDomingosSidineiAlvesMiranda.pdf: 850688 bytes, checksum: ebf1c7ea3222d989fe0dd442d10edd33 (MD5)
Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-06-01T21:18:27Z (GMT) No. of bitstreams: 1 2015_WilsonDomingosSidineiAlvesMiranda.pdf: 850688 bytes, checksum: ebf1c7ea3222d989fe0dd442d10edd33 (MD5)
Made available in DSpace on 2016-06-01T21:18:28Z (GMT). No. of bitstreams: 1 2015_WilsonDomingosSidineiAlvesMiranda.pdf: 850688 bytes, checksum: ebf1c7ea3222d989fe0dd442d10edd33 (MD5)
Um dos principais problemas da álgebra linear computacional é o problema de autovalor, Au = lu, onde A é usualmente uma matriz de ordem grande. A maneira mais efetiva de resolver tal problema consiste em reduzir a matriz A para a forma tridiagonal e usar o método da bissecção ou algoritmo QR para encontrar alguns ou todos os autovalores. Este trabalho apresenta uma implementação em paralelo utilizando uma combinação dos métodos da bissecção, secante e Newton-Raphson para a solução de problemas de autovalores de matrizes hermitianas. A implementação é voltada para unidades de processamentos gráficos (GPUs) visando a utilização em computadores que possuam placas gráficas com arquitetura CUDA. Para comprovar a eficiência e aplicabilidade da implementação, comparamos o tempo gasto entre os algoritmos usando a GPU, a CPU e as rotinas DSTEBZ e DSTEVR da biblioteca LAPACK. O problema foi dividido em três fases, tridiagonalização, isolamento e extração, as duas últimas calculadas na GPU. A tridiagonalização via DSYTRD da LAPACK, calculada em CPU, mostrou-se mais eficiente do que a realizada em CUDA via DSYRDB. O uso do método zeroinNR na fase de extração em CUDA foi cerca de duas vezes mais rápido que o método da bissecção em CUDA. Então o método híbrido é o mais eficiente para o nosso caso. _______________________________________________________________________________________________ ABSTRACT
One of the main problems in computational linear algebra is the eigenvalue problem Au = lu, where A is usually a matrix of big order. The most effective way to solve this problem is to reduce the matrix A to tridiagonal form and use the method of bisection or QR algorithm to find some or all of the eigenvalues. This work presents a parallel implementation using a combination of methods bisection, secant and Newton-Raphson for solving the eigenvalues problem for Hermitian matrices. Implementation is focused on graphics processing units (GPUs) aimed at use in computers with graphics cards with CUDA architecture. To prove the efficiency and applicability of the implementation, we compare the time spent between the algorithms using the GPU, the CPU and DSTEBZ and DSTEVR routines from LAPACK library. The problem was divided into three phases, tridiagonalization, isolation and extraction, the last two calculated on the GPU. The tridiagonalization by LAPACK’s DSYTRD, calculated on the CPU, proved more efficient than the DSYRDB in CUDA. The use of the method zeroinNR on the extraction phase in CUDA was about two times faster than the bisection method in CUDA. So the hybrid method is more efficient for our case.

O presente trabalho apresenta um estudo do método de divisão-e-conquista para solução dos auto-sistemas de matrizes tridiagonais simétricas. Inicialmente, explanamos a parte teórica, e posteriormente, por meio de exemplos numéricos mostramos seu funcionamento. Para a realização deste estudo, utilizou-se o software Maple como ferramenta auxiliar. Realizamos comparações e análises dos auto-sistemas encontrados com as rotinas DSTEDC e DSTEQR do LAPACK, que utilizam respectivamente o método de divisão-e-conquista e o método QR e também comparamos estes com os resultados encontrados por nós. Verificamos por meio de testes os tempos, que as rotinas citadas, dispendem na resolução de alguns auto-sistemas. Os resultados apresentados mostram que o método de Divisão-e-Conquista é competitivo com o método tradicional, QR, para o cálculo de autovalores e autovetores de matrizes tridiagonais simétricas.

碩士
國立中山大學
應用數學研究所
83
Tridiagonal Matrices are special square matrices. Their nonzero elements only occure at diagonals and subdiagonals. Other entries are zero. Such matrices play an important role in matrix theory and matrix computation. This paper consider such matrix as a function of its diagonal vector, that is, the subdiagonals are fixed constants. If we consider the set of all vectors such that the value of this function is a singular matrix, then this set will be the union of n disjoint surfaces in n dimensional space and each surface is a connected closed set. We will explore the geometric properties of these surfaces. Moreover, the set of all vectors such that the value of the function is a nonsingular matrix and the geometric meaning of eigenvalues will also be discussed in this paper.

碩士
東吳大學
數學系
91
Let A be an n-by-n tridiagonal matrix with zero main diagonal. When n=3, 4, 5, we give a necessary and sufficient condition for the numerical range of A to be a circular disk centered at the origin. Necessary conditions for higher dimension are expected to described from the previous patterns.

碩士
國立清華大學
數學研究所
77
This paper is concerned with tridiagonal matrices of the form ┌ ┐ │g(1) 1 │ │ 1 g(2) 1 │ 　　A(g)=│ . . . │. │ 1 g(n-1) 1 │ │ 1 g(n)│ └ ┘ where g=(g(1),g(2),...,g(n)) is a real vector in Rn. We treat such a matrix as a function of its diagonal vector g=(g(1),g(2),...,g(n)) and investigate, by means of a three-term recurrence relation, the properties of a partition of Rn which consists of "regular domains" and "singular surfaces" with respect to A(g). In particular, properties related to geometrical, topological, symmetry and oscillatory properties of a general partition are given, and analytic estimates of the sizes of the regular domains, as well as existence and localization of eigenvalues related to linear and nonlinear difference eigenvalue problems are derived as application.

碩士
國立政治大學
數學研究所
92
The QR algorithm is a popular method for computing all the eigenvalues of a dense matrix. If we use a proper shift, we can accelerate convergence of the iterative process. Hence, we design a new shift strategy which includes an eigenvalue of the trailing principal 3-by-3 submatrix of the tridiagonal matrix. We prove the global convergence of the new strategy. In other words, the purpose of this thesis is to propose a theory of the convergence of a new shifted QR algorithm.

碩士
國立中山大學
資訊工程研究所
84
Due to the extremely high cost of supercomputers and the popularity of network-connected worksations, many computation- intensive scientific problems previously only executable on dedicated supercomputers can now be computed within satisfactory time on a cluster of workstations with the aid of Parallel Virtual Machine(PVM), a public domain package for easy implementation of parallel programs. Finding eigenvalues of symmetric matrices is one of the fundamental problems in many scientific and engineering computations , and usually take a significant portion of the total execution time. The split-and- merge algorithm with Laguerre iterations is selected to slove the eigenvalue problem of tridiagonal symmetric matrices on worksation clusters. Due to its high parallelism and low communication overhead. Furthermore, dynamic load balancing is also considered in order to increase the efficiecy of distributed computing. The experimental results show promising speedup comparied to the sequential implemnetation.

碩士
國立中山大學
應用數學研究所
85
To compute the eigenvalues of two special matrices, the symmetric circulant tridiagonal matrix and the symmetric quindiagonal matrix, in this thesis, we propose parallel algorithms based on the bisection method and the Sylvester's law of inertia on these two kinds matrices. The algorithm can be used for calculating some specified eigenvalues of the symmetric tridiagonal matrix. When we apply it on these two kinds matrices, we get a simpler method than the determination notation for the matrix eigenvalue problem.

Tese de mestrado, Matemática Financeira, Universidade de Lisboa, Faculdade de Ciências, 2016
Nesta tese, apresentam-se métodos para resolver numericamente equações diferenciais por forma a obter preços de contractos financeiros. Em particular, dá-se ênfase a opções vanilla de estilo europeu e americano cujo activo subjacente segue um modelo de difusão com saltos. Quanto à distribuição destes útltimos, destacam-se o modelo de Merton, que considera que eles têm uma distribuição Normal, e o de Kou, onde é assumida uma dupla distribuição exponencial. Este tipo de modelos representa uma extensão dos clássicos modelos de difusão, como o famoso modelo de Black-Scholes-Merton, e tem como objectivo superar algumas das falhas inerentes a este último, tal como caudas muito curtas e picos baixos da distribuição do logaritmo dos retornos do activo, que não reflectem, em geral, o sentimento dos investores nos mercados financeiros, aliando, ao mesmo tempo, a simplicidade e eficiência dos modelos de difusão. Para alcançar o nosso objectivo, estabelece-se inicialmente qual é a equação que descreve a dinâmica do valor dos preços das opções referidas em relação a vários parâmetros, tal como o valor do preço do activo subjacente e o tempo até à maturidade. Em seguida, constróem-se partições para a resolução numérica do problema, através da discretização da função que descreve o preço do contracto financeiro por diferenças finitas. Esta abordagem é útil visto que permite obter preços de contractos cujo "payoff" não é tão simples quanto o de opções vanilla e para os quais não existem fórmulas fechadas ou semi-fechadas para o seu valor em cada momento do tempo até à sua maturidade. No final, expõem-se os resultados encontrados para diferentes resoluções das partições, comparados com referências da literatura, e apresentam-se algumas conclusões.
In this dissertation, methods to solve numerically partial differential equations in order to obtain prices for contingent claims are presented. In particular, we highlight European and American style vanilla options, whose underlying asset follows a jumpdiffusion model. For the distribution of the jumps, the Merton and Kou models are studied. The former considers these have a Normal distribution, whereas the latter assumes a double-exponential. These type of models represent an extension of the classic diffusion models, such as the famous Black-Scholes-Merton, and has the goal of overcoming its flaws, such as thin tails and low peaks in the distribution of the logarithm of the asset returns, that do not reflect the general investors sentiment in the financial markets, while maintaining the simplicity and tractability inherent to diffusion models. To accomplish our goal, an equation describing the relation of the value of the referred options on several parameters, such as the time-to-maturity and the spot value of the underlying asset is suggested. We then build partitions in order to numerically solve our problem using finite differences, discretizing the function which provides the price of our contingent claim. This approach is useful, since it allows to obtain prices of contracts whose payoff is not as simple as the vanilla options’ and for which it does not exist closed or semi-closed formulae for its value at each point in time until maturity. Finally, we expose results found for each one of partitions considered, comparing them with values in the literature, and some conclusions are presented.