Dissertations / Theses on the topic 'Polynomial product'
To see the other types of publications on this topic, follow the link: Polynomial product.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 31 dissertations / theses for your research on the topic 'Polynomial product.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Wise, Steven M. "POLSYS_PLP: A Partitioned Linear Product Homotopy Code for Solving Polynomial Systems of Equations." Thesis, Virginia Tech, 1998. http://hdl.handle.net/10919/36933.
Full textAbstract:
Globally convergent, probability-one homotopy methods have proven to be very effective for finding all the isolated solutions to polynomial systems of equations. After many years of development, homotopy path trackers based on probability-one homotopy methods are reliable and fast. Now, theoretical advances reducing the number of homotopy paths that must be tracked, and in the handling of singular solutions, have made probability-one homotopy methods even more practical. This thesis describes the theory behind and performance of the new code POLSYS_PLP, which consists of Fortran 90 modules for finding all isolated solutions of a complex coefficient polynomial system of equations by a probability-one homotopy method. The package is intended to be used in conjunction with HOMPACK90, and makes extensive use of Fortran 90 derived data types to support a partitioned linear product (PLP) polynomial system structure. PLP structure is a generalization of m-homogeneous structure, whereby each component of the system can have a different m-homogeneous structure. POLSYS_PLP employs a sophisticated power series end game for handling singular solutions, and provides support for problem definition both at a high level and via hand-crafted code. Different PLP structures and their corresponding Bezout numbers can be systematically explored before committing to root finding.Master of Science
2
MATSUMOTO, KOHJI. "ON THE MEAN SQUARE OF THE PRODUCT OF ζ(s) AND A DIRICHLET POLYNOMIAL." Rikkyo Daigaku, 2004. http://hdl.handle.net/2237/20071.
Full text
3
Wang, Ting. "Algorithms for parallel and sequential matrix-chain product problem." Ohio : Ohio University, 1997. http://www.ohiolink.edu/etd/view.cgi?ohiou1184355429.
Full text
4
Araaya, Tsehaye. "The Symmetric Meixner-Pollaczek polynomials." Doctoral thesis, Uppsala University, Department of Mathematics, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-3501.
Full textAbstract:
The Symmetric Meixner-Pollaczek polynomials are considered. We denote these polynomials in this thesis by pn(λ)(x) instead of the standard notation pn(λ) (x/2, π/2), where λ > 0. The limiting case of these sequences of polynomials pn(0) (x) =limλ→0 pn(λ)(x), is obtained, and is shown to be an orthogonal sequence in the strip, S = {z ∈ ℂ : −1≤ℭ (z)≤1}.
From the point of view of Umbral Calculus, this sequence has a special property that makes it unique in the Symmetric Meixner-Pollaczek class of polynomials: it is of convolution type. A convolution type sequence of polynomials has a unique associated operator called a delta operator. Such an operator is found for pn(0) (x), and its integral representation is developed. A convolution type sequence of polynomials may have associated Sheffer sequences of polynomials. The set of associated Sheffer sequences of the sequence pn(0)(x) is obtained, and is found
to be ℙ = {{pn(λ) (x)} =0 : λ ∈ R}. The major properties of these sequences of polynomials are studied.
The polynomials {pn(λ) (x)}∞n=0, λ < 0, are not orthogonal polynomials on the real line with respect to any positive real measure for failing to satisfy Favard’s three term recurrence relation condition. For every λ ≤ 0, an associated nonstandard inner product is defined with respect to which pn(λ)(x) is orthogonal.
Finally, the connection and linearization problems for the Symmetric Meixner-Pollaczek polynomials are solved. In solving the connection problem the convolution property of the polynomials is exploited, which in turn helps to solve the general linearization problem.
5
DE, PICCOLI ALESSANDRO. "OPTIMIZED REPRESENTATIONS IN CRYPTOGRAPHIC PRIMITIVES." Doctoral thesis, Università degli Studi di Milano, 2022. http://hdl.handle.net/2434/932549.
Full textAbstract:
Il lavoro di tesi si focalizza sull'ottimizzazione di primitive crittografiche sia dal punto di vista teorico che da quello pratico. Riguardo il punto di vista teorico sarà analizzato il problema dell'accelerazione degli algoritmi di moltiplicazione polinomiale, ampiamente impiegati in Crittografia Post-Quantum, come, ad esempio, NTRU e McEliece. Quest'ultimo, in particolare, utilizza campi di Galois e loro estensioni, i cui elementi possono essere rappresentati in forma polinomiale. Saranno dunque esposte nuove tecniche che permettono una riduzione del numero di porte logiche e verranno presentati i risultati sperimentali della loro applicazione all'implementazione del cifrario McEliece attualmente candidato come nuovo standard Post-Quantum al NIST. Dal punto di vista pratico, questo lavoro di tesi, si focalizza sull’ottimizzazione di attacchi alla prima pre-immagine dell'algoritmo di hash SHA-1 basati su SAT solvers. Nessuna delle rappresentazioni testate ha mostrato una particolare efficienza in termini di velocità di risoluzione. Al contrario, un'accurata scelta di valori ha permesso di raggiungere un nuovo stato dell'arte, rivelando al contempo la debolezza di alcune pre-immagini.This work focuses on optimization of cryptographic primitives both in theory and in applications. From a theoretical point of view, it addresses the problem of speeding up the polynomial multiplication used in Post-Quantum cryptosystems such as NTRU and McEliece. In particular, the latter extensively uses Galois fields whose elements can be represented in polynomial form. After presenting the reduction of the number of gates for polynomial multiplication through new techniques, in this work experimental results of such techniques applied to the current implementation of McEliece will be presented. From a practical point of view, this work focuses on the optimization of a SAT solver-based preimage attack against SHA-1 and on its strength. None of the tested representations of SHA-1 seems to be competitive in terms of resolution. On the contrary, an accurate choice of some pre-image bits allows one to reach a better state of art, revealing meanwhile the weakness of some pre-images.
6
Tsang, Chiu-yin, and 曾超賢. "Finite Blaschke products versus polynomials." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2012. http://hub.hku.hk/bib/B4784971X.
Full textAbstract:
The objective of the thesis is to compare polynomials and finite Blaschke products, and demonstrate that they share many similar properties and hence we can
establish a dictionary between these two kinds of finite maps for the first time.
The results for polynomials were reviewed first. In particular, a special kind of
polynomials was discussed, namely, Chebyshev polynomials, which can be defined
by the trigonometric cosine function cos ?. Also, a complete classification for two
polynomials sharing a set was given.
In this thesis, some analogous results for finite Blaschke products were proved.
Firstly, Chebyshev-Blaschke products were introduced. They can be defined by re-
placing the trigonometric cosine function cos z by the Jacobi cosine function cd(u; ? ).
They were shown to have several similar properties of Chebyshev polynomials, for
example, both of them share the same monodromy, satisfy some differential equations and solve some minimization problems. In addition, some analogous results
about two finite Blaschke products sharing a set were proved, based on Dinh's and
Pakovich's ideas.
Moreover, the density of prime polynomials was investigated in two different
ways: (i) expressing the polynomials of degree n in terms of the zeros and the leading
coefficient; (ii) expressing the polynomials of degree n in terms of the coefficients.
Also, the quantitative version of the density of composite polynomials was developed
and a density estimate on the set of composite polynomials was given. Furthermore,
some analogous results on the the density of prime Blaschke products were proved.published_or_final_version
Mathematics
Doctoral
Doctor of Philosophy
7
CAMPOS, Suene Ferreira. "Teorema sobre o produto tensorial em característica positiva." Universidade Federal de Campina Grande, 2008. http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/1207.
Full textAbstract:
Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-22T13:41:27Z
No. of bitstreams: 1
SUENE FERREIRA CAMPOS - DISSERTAÇÃO PPGMAT 2008..pdf: 741113 bytes, checksum: 7fc13ffd22412553f540977137401f24 (MD5)Made available in DSpace on 2018-07-22T13:41:27Z (GMT). No. of bitstreams: 1 SUENE FERREIRA CAMPOS - DISSERTAÇÃO PPGMAT 2008..pdf: 741113 bytes, checksum: 7fc13ffd22412553f540977137401f24 (MD5) Previous issue date: 2008-12
Neste trabalho apresentamos um estudo sobre o comportamento das identidades polinomiais dos produtos tensoriais de álgebras T-primas sobre corpos infinitos com diferentes características. Mais precisamente, apresentamos o Teorema sobre Produto Tensorial (TPT), descrito por Kemer para corpos de característica zero, e verificamos a sua validade sobre corpos infinitos com característica positiva. Incialmente, a partir de resultados apresentados por Azevedo e Koshlukov, estudamos os T-ideais das álgebras M1,1(G) eG⊗G, para corpos infinitos com característica zero e característicap > 2. Aqui, G = G0⊕G1 é a álgebra de Grassmann de dimensão infinita eM1,1(G) é a subálgebra de M2(G) que consiste das matrizes de ordem 2 que têm na diagonal principal entradas emG0 e na diagonal secundária entradas emG1. Em seguida, utilizando métodos introduzidos por Regev e desenvolvidos por Azevedo, Fidélis e Koshlukov, verificamos a validade do TPT para corpos de característica positiva, quando o mesmo é restrito a polinômios multilineares. Finalmente, apresentamos alguns resultados obtidos por Alves, Azevedo, Fidélis e Koshlukov, que comprovam que o TPT é falso quando o corpo base é infinito e tem característicap>2.
In this work we present a study about the behavior of polynomial identities of tensor products of T-prime T-ideals over infinite fields of different characteristics. More precisely, we present the Tensor Product Theorem (TPT), described by Kemer for fields of characteristic zero, and verify its validity over infinite fields with positive characteristic. First, based on results of Azevedo and Koshlukov, we study the Tideals of the algebrasM1,1(G) eG⊗G, for infinite fields of characteristic zero and characteristicp>2. Here,G=G0 ⊕G1 is the Grassmann algebra of infinite dimension andM1,1(G) is the subalgebras ofM2(G) consisting of matrices of order2 which main diagonal entries are inG0 and the secondary diagonal entries are inG1. Second, using methods introduced by Regev and developed by Azevedo, Fidélis and Koshlukov, we verify the validity of the TPT for fields of positive characteristic, when it is restricted to multilinear polynomials. Finally, we present some results of Alves, Azevedo, Fidelis and Koshlukov, which show that the TPT is false when the basis field is infinite and has characteristicp>2.
8
Masetti, Masha. "Product Clustering e Machine Learning per il miglioramento dell'accuratezza della previsione della domanda: il caso Comer Industries S.p.A." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2021.
Find full textAbstract:
I lunghi lead time della catena di fornitura cinese dell’azienda Comer Industries S.p.A la obbligano ad ordinare i materiali con sei mesi di anticipo, data in cui spesso i clienti non sono consapevoli dei quantitativi di materiale che necessiteranno.
Al fine di rispondere ai clienti mantenendo l’alto livello di servizio garantito storicamente da Comer Industries, risulta essenziale ordinare il materiale basandosi sulle previsioni della domanda. Tuttavia, attualmente le previsioni non sono sufficientemente accurate. L’obiettivo di questa ricerca è individuare un possibile metodo per incrementare l’accuratezza delle previsioni della domanda.
Potrebbe, al fine del miglioramento della forecast accuracy, incidere positivamente l’utilizzo dell’Intelligenza Artificiale?
Per rispondere alla domanda di ricerca, si sono implementati l’algoritmo K-Means e l’algoritmo Gerarchico in Visual Basic Application al fine di dividere i prodotti in cluster sulla base dei componenti comuni. Successivamente, si sono analizzati gli andamenti della domanda. Implementando differenti algoritmi di Machine Learning su Google Colaboratory, si sono paragonate le accuratezze ottenute e si è individuato un algoritmo di previsione ottimale per ciascun profilo di domanda. Infine, con le previsioni effettuate, si è potuto identificare con il K-means un miglioramento dell’accuracy di circa il 54,62% rispetto all’accuratezza iniziale ed un risparmio del 47% dei costi per il mantenimento del safety stock, mentre con il Clustering Gerarchico si è rilevato un miglioramento dell’accuracy del 11,15% ed un risparmio del 45% dei costi attuali.
Si è, pertanto, concluso che la clusterizzazione dei prodotti potrebbe apportare un contributo positivo all’accuratezza delle previsioni. Inoltre, si è osservato come il Machine Learning potrebbe costituire lo strumento ideale per individuare le soluzioni ottimali sia all’interno degli algoritmi di Clustering sia all’interno dei metodi previsionali.
9
Magnin, Loïck. "Two-player interaction in quantum computing : cryptographic primitives & query complexity." Thesis, Paris 11, 2011. http://www.theses.fr/2011PA112275/document.
Full textAbstract:
Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISMThis dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ``quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ``intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ``quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ``multiplicative adversary method'' is stronger than the ``additive adversary method''. We then show a reduction from the ``polynomial method'' to the multiplicative adversary method. Hence, we prove that the multiplicative adversary method is the strongest one. Adversary methods are usually difficult to use since they involve the computation of norms of matrices with very large size. We show how studying the symmetries of a problem can largely simplify these computations. Last, using these principles we prove the tight lower bound of the INDEX-ERASURE problem. This a quantum state generation problem that has links with the famous GRAPH-ISOMORPHISM problem
10
Piah, Abd Rahni bin Mt. "Construction of smooth closed surfaces by piecewise tensor product polynomials." Thesis, University of Dundee, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.295312.
Full text
11
Magnin, Loick. "Two-player interaction in quantum computing : cryptographic primitives & query complexity." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00676922.
Full textAbstract:
This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ''quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ''intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ''quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ''multiplicative adversary method'' is stronger than the ''additive adversary method''. We then show a reduction from the ''polynomial method'' to the multiplicative adversary method. Hence, we prove that the multiplicative adversary method is the strongest one. Adversary methods are usually difficult to use since they involve the computation of norms of matrices with very large size. We show how studying the symmetries of a problem can largely simplify these computations. Last, using these principles we prove the tight lower bound of the INDEX-ERASURE problem. This a quantum state generation problem that has links with the famous GRAPH-ISOMORPHISM problem.
12
Ennaoui, Karima. "Computational aspects of infinite automata simulation and closure system related issues." Thesis, Université Clermont Auvergne (2017-2020), 2017. http://www.theses.fr/2017CLFAC031/document.
Full textAbstract:
La thèse est consacrée à des problématiques d’algorithmique et de complexité sur deux sujets. Le premier sujet s’intéresse à la composition comportementale des services web. Ce problème a été réduit à la simulation d’un automate par le produit fermé d’un ensemble d’automates. La thèse étudie dans sa première partie la complexité de ce problème en considérant deux paramètres : le nombre des instances considéré de chaque service et la présence des états hybrides : état à la fois intermédiaire et final dans un automate. Le second sujet porte sur les systèmes de fermeture et s’intéresse au calcul de l’extension maximale d’un système de fermeture ainsi qu’à l’énumération des clefs candidates d’une base implicative. On donne un algorithme incrémental polynomial qui génère l’extension maximale d’un treillis codé par une relation binaire. Puis, la notion de key-ideal est définie, en prouvant que leur énumération est équivalente à l’énumération des clefs candidates. Ensuite, on donne un algorithme qui permet de générer les key-ideal minimaux en temps incrémental polynomial et les key-ideal non minimaux en délai polynomialThis thesis investigates complexity and computational issues in two parts. The first concerns an issue related to web services composition problem: Deciding whether the behaviour of a web service can be composed out of an existing repository of web services. This question has been reduced to simulating a finite automata to the product closure of an automata set. We study the complexity of this problem considering two parameters; the number of considered instances in the composition and the presence of the so-called hybrid states (states that are both intermediate and final). The second part concerns closure systems and two related issues; Maximal extension of a closure system : we give an incremental polynomial algorithm that computes a lattice's maximal extension when the input is a binary relation. Candidate keys enumeration : we introduce the notion of key-ideal sets and prove that their enumeration is equivalent to candidate keys enumeration. We then give an efficient algorithm that generates all non-minimal key-ideal sets in a polynomial delay and all minimal ones in incremental polynomial time
13
Fomatati, Yves Baudelaire. "Multiplicative Tensor Product of Matrix Factorizations and Some Applications." Thesis, Université d'Ottawa / University of Ottawa, 2019. http://hdl.handle.net/10393/39913.
Full textAbstract:
An n × n matrix factorization of a polynomial f is a pair of n × n matrices (P, Q) such
that PQ = f In, where In is the n × n identity matrix. In this dissertation, we study matrix
factorizations of an arbitrary element in a given unital ring. This study is motivated on the
one hand by the construction of the unit object in the bicategory LGK of Landau-Ginzburg
models (of great utility in quantum physics) whose 1−cells are matrix factorizations of
polynomials over a commutative ring K, and on the other hand by the existing tensor
product of matrix factorizations b⊗.
We observe that the pair of n × n matrices that appear in the matrix factorization of an
element in a unital ring is not unique. Next, we propose a new operation on matrix factorizations denoted e⊗ which is such that if X is a matrix factorization of an element f in a
unital ring (e.g. the power series ring K[[x1, ..., xr]] f) and Y is a matrix factorization of
an element g in a unital ring (e.g. g ∈ K[[y1, ..., ys]]), then Xe⊗Y is a matrix factorization
of f g in a certain unital ring (e.g. in case f ∈ K[[x1, ..., xr]] and g ∈ K[[y1, ..., ys]], then
f g ∈ K[[x1, ..., xr
, y1, ..., ys]]). e⊗ is called the multiplicative tensor product of X and Y.
After proving that this product is bifunctorial, many of its properties are also stated and
proved.
Furthermore, if MF(1) denotes the category of matrix factorizations of the constant power
series 1, we define the concept of one-step connected category and prove that there is a
one-step connected subcategory of (MF(1),e⊗) which is semi-unital semi-monoidal.
We also define the concept of right pseudo-monoidal category which generalizes the notion of monoidal category and we prove that (MF(1),e⊗) is an example of this concept.
Furthermore, we define a summand-reducible polynomial to be one that can be written
in the form f = t1 + · · · + ts + g11 · · · g1m1 + · · · + gl1 · · · glml
under some specified conditions where each tk
is a monomial and each gji is a sum of monomials. We then use
b⊗ and e⊗ to improve the standard method for matrix factorization of polynomials on this
class and we prove that if pji is the number of monomials in gji, then there is an improved version of the standard method for factoring f which produces factorizations of
size 2
Qm1
i=1
p1i+···+
Qml
i=1
pli−(
Pm1
i=1
p1i+···+
Pml
i=1
pli)
times smaller than the size one would normally obtain with the standard method.
Moreover, details are given to elucidate the intricate construction of the unit object of
LGK. Thereafter, a proof of the naturality of the right and left unit maps of LGK with respect to 2−morphisms is presented. We also prove that there is no direct inverse for these
(right and left) unit maps, thereby justifying the fact that their inverses are found only up
to homotopy. Finally, some properties of matrix factorizations are exploited to state and
prove a necessary condition to obtain a Morita context in LGK.
14
Lahnovych, Carrie. "Analysis and computation of a quadratic matrix polynomial with Schur-products and applications to the Barboy-Tenne model /." Online version of thesis, 2010. http://ritdml.rit.edu/handle/1850/12207.
Full text
15
Hyatt, Matthew. "Quasisymmetric Functions and Permutation Statistics for Coxeter Groups and Wreath Product Groups." Scholarly Repository, 2011. http://scholarlyrepository.miami.edu/oa_dissertations/609.
Full textAbstract:
Eulerian quasisymmetric functions were introduced by Shareshian and Wachs in order to obtain a q-analog of Euler's exponential generating function formula for the Eulerian polynomials. They are defined via the symmetric group, and applying the stable and nonstable principal specializations yields formulas for joint distributions of permutation statistics. We consider the wreath product of the cyclic group with the symmetric group, also known as the group of colored permutations. We use this group to introduce colored Eulerian quasisymmetric functions, which are a generalization of Eulerian quasisymmetric functions. We derive a formula for the generating function of these colored Eulerian quasisymmetric functions, which reduces to a formula of Shareshian and Wachs for the Eulerian quasisymmetric functions. We show that applying the stable and nonstable principal specializations yields formulas for joint distributions of colored permutation statistics. The family of colored permutation groups includes the family of symmetric groups and the family of hyperoctahedral groups, also called the type A Coxeter groups and type B Coxeter groups, respectively. By specializing our formulas to these cases, they reduce to the Shareshian-Wachs q-analog of Euler's formula, formulas of Foata and Han, and a new generalization of a formula of Chow and Gessel.
16
dujardin, romain. "Dynamique d'applications non polynomiales et courants laminaires." Phd thesis, Université Paris Sud - Paris XI, 2002. http://tel.archives-ouvertes.fr/tel-00004028.
Full textAbstract:
Cette thèse est consacrée aux systèmes dynamiques holomorphes en dimension complexe 2, et à la théorie des courants laminaires, qui en est issue. Nous étudions la dynamique d'une classe d'applications holomorphes, introduites par Hubbard et Oberste-Vorth, non nécessairement rationnelles, définies au voisinage du bidisque unité, qui sont aux applications de Hénon complexes ce que les applications d'allure polynomiale sont aux polynômes d' une variable. Nous montrons pour ces applications un certain nombre de propriétés dynamiques analogues à celles des difféomorphismes polynomiaux, établies notamment par Bedford, Lyubich, Smillie, Fornæ ss et Sibony: existence de courants positifs fermés invariants ``attractifs'', ainsi que d'une unique mesure d'entropie maximale, décrivant la répartition des points périodiques de type selle. Les courants laminaires, généralisation des ``cycles feuilletés'' de Sullivan, ont été introduits par Bedford, Lyubich et Smillie dans le cadre de l'étude des difféomorphismes polynomiaux de deux variables. Nous développons une théorie générale de ces courants. Premièrement nous donnons un critère géométrique portant sur une suite de courbes planes algébriques de degré tendant vers l'infini pour que ses valeurs d'adhérence au sens des courants soient laminaires, et en déduisons la laminarité du courant dynamique ``de Green'' pour une classe d'applications rationnelles du plan projectif, incluant celle des applications birationnelles. Pour les courants obtenus par ce procédé, nous montrons que l'on peut donner, sous une hypothèse de nature potentialiste, une interprétation géométrique au produit extérieur; nous montrons également que ces courants satisfont une propriété de ``prolongement analytique''. Ceci nous permet de réaliser ces courants comme cycles feuilletés sur une lamination abstraite.
17
Durvye, Clémence. "Algorithmes pour la décomposition primaire des idéaux polynomiaux de dimension nulle donnés en évaluation." Phd thesis, Université de Versailles-Saint Quentin en Yvelines, 2008. http://tel.archives-ouvertes.fr/tel-00275219.
Full textAbstract:
Les algorithmes de résolution polynomiale sont impliqués dans des outils sophistiqués de calcul en géométrie algébrique aussi bien quen ingénierie. Les plus populaires dentre eux reposent sur des bases de Gröbner, des matrices de Macaulay ou des décompositions triangulaires. Dans tous ces algorithmes, les polynômes sont développés dans une base des monômes et les calculs utilisent essentiellement des routines dalgèbre linéaire. L'inconvénient majeur de ces méthodes est lexplosion exponentielle du nombre de monômes apparaissant dans des polynômes éliminants. De manière alternative, lalgorithme Kronecker manie des polynômes codés comme la fonction qui calcule ses valeurs en tout point.Dans cette thèse, nous donnons une présentation concise de ce dernier algorithme, ainsi qu'une preuve autonome de son bon fonctionnement. Toutes nos démonstrations sont intimement liées aux algorithmes, et ont pour conséquence des résultats classiques en géométrie algébrique, comme un théorème de Bézout. Au delà de leur intérêt pédagogique, ces preuves permettent de lever certaines hypothèses de régularité, et donc d'étendre l'algorithme au calcul des multiplicités sans coût supplémentaire.
Ensuite, nous présentons un algorithme de décomposition primaire pour les idéaux de polynômes de dimension nulle. Nous en donnerons également une étude de complexité précise, complexité qui est polynomiale en le nombre de variables, en le coût dévaluation du système, et en un nombre de Bézout.
18
Lund, Kathryn. "A new block Krylov subspace framework with applications to functions of matrices acting on multiple vectors." Diss., Temple University Libraries, 2018. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/493337.
Full textAbstract:
MathematicsPh.D.
We propose a new framework for understanding block Krylov subspace methods, which hinges on a matrix-valued inner product. We can recast the ``classical" block Krylov methods, such as O'Leary's block conjugate gradients, global methods, and loop-interchange methods, within this framework. Leveraging the generality of the framework, we develop an efficient restart procedure and error bounds for the shifted block full orthogonalization method (Sh-BFOM(m)). Regarding BFOM as the prototypical block Krylov subspace method, we propose another formalism, which we call modified BFOM, and show that block GMRES and the new block Radau-Lanczos method can be regarded as modified BFOM. In analogy to Sh-BFOM(m), we develop an efficient restart procedure for shifted BGMRES with restarts (Sh-BGMRES(m)), as well as error bounds. Using this framework and shifted block Krylov methods with restarts as a foundation, we formulate block Krylov subspace methods with restarts for matrix functions acting on multiple vectors f(A)B. We obtain convergence bounds for \bfomfom (BFOM for Functions Of Matrices) and block harmonic methods (i.e., BGMRES-like methods) for matrix functions. With various numerical examples, we illustrate our theoretical results on Sh-BFOM and Sh-BGMRES. We also analyze the matrix polynomials associated to the residuals of these methods. Through a variety of real-life applications, we demonstrate the robustness and versatility of B(FOM)^2 and block harmonic methods for matrix functions. A particularly interesting example is the tensor t-function, our proposed definition for the function of a tensor in the tensor t-product formalism. Despite the lack of convergence theory, we also show that the block Radau-Lanczos modification can reduce the number of cycles required to converge for both linear systems and matrix functions.
Temple University--Theses
19
Bonfim, Rafaela Neves. "Núcleos isotrópicos e positivos definidos sobre espaços 2-homogêneos." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/55/55135/tde-22092017-105842/.
Full textAbstract:
Este trabalho é composto de duas partes distintas, ambas dentro de um mesmo tema: núcleos positivos definidos sobre variedades. Na primeira delas fornecemos uma caracterização para os núcleos contínuos, isotrópicos e positivos definidos a valores matriciais sobre um espaço compacto 2-homogêneo. Utilizando-a, investigamos a positividade definida estrita destes núcleos, apresentando inicialmente algumas condições suficientes para garantir tal propriedade. No caso em que o espaço 2-homogêneo não é uma esfera, descrevemos uma caracterização definitiva para a positividade definida estrita do núcleo. Neste mesmo caso, para núcleos a valores no espaço das matrizes de ordem 2, apresentamos uma caraterização alternativa para a positividade definida estrita do núcleo via os dois elementos na diagonal principal da representação matricial do núcleo. Na segunda parte, nos restringimos a núcleos positivos definidos escalares sobre os mesmos espaços e determinamos condições necessárias e suficientes para a positividade definida estrita de um produto de núcleos positivos definidos sobre um mesmo espaço compacto 2-homogêneo. Apresentamos ainda uma extensão deste resultado para núcleos positivos definidos sobre o produto cartesiano de um grupo localmente compacto com uma esfera de dimensão alta, mantendo-se a isotropia na componente esférica.In this work we present a characterization for the continuous, isotropic and positive definite matrix-valued kernels on a compact two-point homogeneous space. After that, we consider the strict positive definiteness of the kernels, describing some independent sufficient conditions for that property to hold. In the case the space is not a sphere, one of the conditions becomes necessary and sufficient for the strict positive definiteness of the kernel. Further, for 22- matrix-valued kernels on a compact two-point homogeneous space which is not a sphere, we present a characterization for the strict positive definiteness of the kernels based upon the main diagonal elements in its matrix representation. In the last part of this work, we restrict ourselves to scalar kernels and determine necessary and sufficient conditions in order that the product of two continuous, isotropic and positive definite kernels on a compact two-point homogeneous space be strictly positive definite. We also discuss the extension of this result for kernels defined on a product of a locally compact group and a high dimensional sphere.
20
Bostan, Alin. "Algorithmique efficace pour des opérations de base en calcul formel." Phd thesis, Ecole Polytechnique X, 2003. http://pastel.archives-ouvertes.fr/pastel-00001023.
Full textAbstract:
Le sujet de cette thèse est la conception et l'implantation d'algorithmes efficaces pour des opérations de base en calcul formel, ainsi que leurs applications à des domaines connexes, comme la théorie algorithmique des nombres et la cryptographie. Une première partie traite de l'algorithmique de base sur les polynômes à une variable. L'outil systématiquement mis en oeuvre est une version constructive du principe de transposition de Tellegen, qui permet d'obtenir de nouveaux algorithmes pour l'évaluation multipoint et l'interpolation (dans diverses bases polynomiales et pour diverses familles de points d'évaluation), ainsi qu'un théorème d'équivalence entre les complexités de ces deux problèmes. La deuxième partie est consacrée à l'algorithmique des nombres algébriques. Nous étudions d'abord certaines opérations élémentaires, comme la somme, le produit et leur généralisation, le produit diamant de Brawley et Carlitz. Leur calcul repose sur l'utilisation de l'opérateur de Newton formel et de la dualité algébrique, traduite algorithmiquement par l'emploi du principe de transposition et des méthodes de type pas de bébés / pas de géants. Ces méthodes sont ensuite généralisées au cadre des systèmes de polynômes de dimension zéro, pour le calcul de polynômes minimaux dans des algèbres quotient, ainsi que de paramétrisations rationnelles. Dans la troisième partie, nous étudions la question du calcul d'un terme d'une suite récurrente linéaire à coefficients polynomiaux. Comme application, nous obtenons des améliorations théoriques et pratiques des méthodes de comptage de points utilisées en cryptographie. Nous proposons ensuite une méthode de type évaluation-interpolation pour certaines opérations usuelles sur les opérateurs différentiels linéaires à coefficients polynomiaux.
21
Ould, Mohamed Abdel Haye Mohamedou. "Théorèmes limites pour des processus à longue mémoire saisonnière." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2001. http://tel.archives-ouvertes.fr/tel-00001326.
Full textAbstract:
Nous étudions le comportement asymptotique de statistiques ou fonctionnelles liées à des processus à longue mémoire saisonnière. Nous nous concentrons sur les lignes de Donsker et sur le processus empirique. Les suites considérées sont de la forme $G(X_n)$ où $(X_n)$ est un processus gaussien ou linéaire. Nous montrons que les résultats que Taqqu et Dobrushin ont obtenus pour des processus à longue mémoire dont la covariance est à variation régulière à l'infini peuvent être en défaut en présence d'effets saisonniers. Les différences portent aussi bien sur le coefficient de normalisation que sur la nature du processus limite. Notamment nous montrons que la limite du processus empirique bi-indexé, bien que restant dégénérée, n'est plus déterminée par le degré de Hermite de la fonction de répartition des données. En particulier, lorsque ce degré est égal à 1, la limite n'est plus nécessairement gaussienne. Par exemple on peut obtenir une combinaison de processus de Rosenblatt indépendants. Ces résultats sont appliqués à quelques problèmes statistiques comme le comportement asymptotique des U-statistiques, l'estimation de la densité et la détection de rupture.
22
Chemli, Zakaria. "Développements combinatoires autour des tableaux et des nombres eulériens." Thesis, Paris Est, 2017. http://www.theses.fr/2017PESC1055/document.
Full textAbstract:
Cette thèse se situe au carrefour de la combinatoire énumérative, algébrique et bijective. Elle se consacre d’une part à traduire des problèmes algébriques en des problèmes combinatoires, et inversement, utilise le formalisme algébrique pour traiter des questions combinatoires.Après un rappel des notions classiques de combinatoire et de structures algébriques, nous abordons l’étude des tableaux de dominos décalés, qui sont des objets combinatoires définis dans le but de mieux comprendre la combinatoire des fonctions symétriques P et Q de Schur. Nous donnons la définition de ces tableaux et nous démontrons qu'ils sont en bijection avec les paires de tableaux de Young décalés. Cette bijection nous permet de voir ces objets comme des éléments du super monoïde plaxique décalé, qui est l'analogue décalé du super monoïde plaxique de Carré et Leclerc. Nous montrons aussi que ces tableaux décrivent un produit de deux fonctions P de Schur et en prenant un autre type de tableaux de dominos décalés, nous décrivons un produit de deux fonctions Q de Schur. Nous proposons aussi deux algorithmes d'insertion pour les tableaux de dominos décalés, analogues aux algorithmes d'insertion mixte et d'insertion gauche-droit de Haiman. Toujours dans le domaine de la combinatoire bijective, nous nous intéressons dans la deuxième partie de notre travail à des bijections en lien avec des statistiques sur les permutations et les nombres eulériens.Dans cette deuxième partie de thèse, nous introduisons l'unimodalité des suites finies associées aux différentes directions dans le triangle eulérien. Nous donnons dans un premier temps une interprétation combinatoire ainsi que la relation de récurrence des suites associées à la direction (1,t) dans le triangle eulérien, où t≥1. Ces suites sont les coefficients de polynômes appelés les polynômes eulériens avec succession d'ordre t, qui généralisent les polynômes eulériens. Nous démontrons par une bijection entre les permutations et des chemins nord-est étiquetés que ces suites sont log-concaves et donc unimodales. Puis nous prouvons que les suites associées aux directions (r,q), où r est un entier positif et q est un entier, tel que r+q≥0, sont aussi log-concaves et donc unimodalesThis thesis is at the crossroads of enumerative, algebraic and bijective combinatorics. It studies some algebraic problems from a combinatorial point of view, and conversely, uses algebraic formalism to deal with combinatorial questions.After a reminder about classical notions of combinatoics and algebraic structures, We introduce new combinatorial objects called the shifted domino tableaux, these objects can be seen as a shifted analog of domino tableaux or as an extension of shifted Young tableaux. We prove that these objects are in bijection with pairs of shifted Young tableaux. This bijection shows that shifted domino tableaux can be seen as elements of the super shifted plactic monoid, which is the shifted analog of the super plactic monoid. We also show that the sum over all shifted domino tableaux of a fixed shape describe a product of two P-Schur functions, and by taking a different kind of shifted domino tableaux we describe a product of two Q-Schur functions. We also propose two insertion algorithms for shifted domino tablaux, analogous to Haiman's left-right and mixed insertion algorithms. Still in the field of bijective combinatorics, we are interested in the second part of our work with bijections related to statistics on permutations and Eulerian numbers.In this second part of this thesis, we introduce the unimodality of finite sequences associated to different directions in the Eulerian triangle. We first give a combinatorial interpretations as well as recurrence relations of sequences associated with the direction (1, t) in the Eulerian triangle, where t≥1. These sequences are the coefficients of polynomials called the t-successive eulerian polynomials, which generalize the eulerian polynomials. We prove using a bijection between premutations and north-east lattice paths that those sequences are unomodal. Then we prove that the sequences associated with the directions (r, q), where r is a positive integer and q is an integer such that r + q ≥ 0, are also log-concave and therefore unimodal
23
Pasca, Bogdan Mihai. "Calcul flottant haute performance sur circuits reconfigurables." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2011. http://tel.archives-ouvertes.fr/tel-00654121.
Full textAbstract:
De plus en plus de constructeurs proposent des accélérateurs de calculs à base de circuits reconfigurables FPGA, cette technologie présentant bien plus de souplesse que le microprocesseur. Valoriser cette flexibilité dans le domaine de l'accélération de calcul flottant en utilisant les langages de description de circuits classiques (VHDL ou Verilog) reste toutefois très difficile, voire impossible parfois. Cette thèse a contribué au développement du logiciel FloPoCo, qui offre aux utilisateurs familiers avec VHDL un cadre C++ de description d'opérateurs arithmétiques génériques adapté au calcul reconfigurable. Ce cadre distingue explicitement la fonctionnalité combinatoire d'un opérateur, et la problématique de son pipeline pour une précision, une fréquence et un FPGA cible donnés. Afin de pouvoir utiliser FloPoCo pour concevoir des opérateurs haute performance en virgule flottante, il a fallu d'abord concevoir des blocs de bases optimisés. Nous avons d'abord développé des additionneurs pipelinés autour des lignes de propagation de retenue rapides, puis, à l'aide de techniques de pavages, nous avons conçu de gros multiplieurs, possiblement tronqués, utilisant des petits multiplieurs. L'évaluation de fonctions élémentaires en flottant implique souvent l'évaluation en virgule fixe d'une fonction. Nous présentons un opérateur générique de FloPoCo qui prend en entrée l'expression de la fonction à évaluer, avec ses précisions d'entrée et de sortie, et construit un évaluateur polynomial optimisé de cette fonction. Ce bloc de base a permis de développer des opérateurs en virgule flottante pour la racine carrée et l'exponentielle qui améliorent considérablement l'état de l'art. Nous avons aussi travaillé sur des techniques de compilation avancée pour adapter l'exécution d'un code C aux pipelines flexibles de nos opérateurs. FloPoCo a pu ainsi être utilisé pour implanter sur FPGA des applications complètes.
24
Williamson, John M. H. "Transfer matrix factorization using product-form polynomial scattering parameters." 1987. http://hdl.handle.net/1993/24287.
Full text
25
Moeen, Kareem. "Progressive product reduction for polynomial basis multiplication over GF(3m)." Thesis, 2016. http://hdl.handle.net/1828/7657.
Full textAbstract:
Galois fields are essential blocks of building many of cryptographic schemes. The main advantage of applying Galois fields over cryptographic applications are to reduce cost and increase the sufficiency of the performance. In past, they were interested in implement Galois field of characteristic 2 in most of the crypto-system application, but in the meantime, the researcher started to work on Galois field of odd characteristics which it has applications in many areas like Elliptic Curve Cryptography, Identity-based Encryption, Short Signature Schemes and etc.
In this thesis, an odd characteristic Galois field was implemented. In particular, this
thesis focuses on implementation of multiplication and reduction on GF(3m). Overview
about the thesis idea was presented in the beginning. Finite field arithmetic was discussed where it shows some of the Galois fields important definitions and properties. In addition, irreducible polynomials over GF(p) where p is prime and the basic additional and multiplication over GF(pm) was discussed as well. Introduction to the proposed implementation started with the arithmetic of the Galois field characteristics 3. The problem formulation introduced by its mathematical representation and the Progressive Product Reduction (PPR) technique which is the technique used in this thesis. Implement three different semi-systolic arrays architecture with different projection functions. This stage followed by modeling assumption for complexity analysis for both area and delay where it used to compare proposed designs with other published designs. Proposed design gets verified by Matlab code implementation at the end of this thesis.Graduate
Kareem.moeen@gmail.com
26
Nia, Ali. "VHDL Implementation of PPR Systolic Array Architecture for Polynomial GF(2^m) Multiplication." Thesis, 2013. http://hdl.handle.net/1828/4575.
Full textAbstract:
This thesis is devoted to efficient VHDL design of Systolic Array Architecture for Polynomial GF(2^m) multiplication. The hardware implements the Processor Elements(PE) and Systolic Array design for Progressive Product Reduction (PPR) method proposed by Gebali and Atef. The experiment first implements a simpler irreducible polynomials GF(2^5) based on the defined algorithms for PPR in order to confirm the functionality of the design and then tries the bigger value of m for GF(2^133) and GF(2^233), recommended by NIST. The thesis is comparing the three designs based on their power consumption, Maximum Data path delay and device utilization. It also looking in to the different optimization method for the designs and recommends a design optimization based on circuit modification.Graduate
0544
alinia@uvic.ca
27
Chen, Hung-Ming, and 陳宏明. "Analyzing consumer’s preference and perceptions of product form by polynomial networks-using cell phone design as an example." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/94698930675484784430.
Full textAbstract:
碩士華梵大學
工業設計系碩士班
96
It is a core competition ability on product form design to get user’s needs and perceptual cognition data efficiently. In the past, most of the data came from customer survey, which is time and energy consuming in the collection and analysis of the marketing study. Consequently, it causes lower competition and substantial burdens in manpower and costs in product development stage. The main purpose for this research is to develop an efficient approach that can help quantify consumer’s perceptual data into design specifications of product form. In this study, mobile phone design was adopted as an example to quantify consumer’s perceptions of product form in Polynomial Networks. Firstly, Kansei Engineering was used to switch user’s cognition of product styles, from which 20 pairs of image words were extracted from Quantification Type I and Multiple Regression analyses. In this way, designing rules for new mobile phone design, particularly the relationships between image perceptions and form treatments, were specified. Later, the theory of “Polynomial Networks” was adopted to apply the results obtained due to its better performance than linear (multi-variance) model. Some advanced relationships between parameters of and images of product form were then identified. To solve the design problem on human perception, and to help designers meet consumers’ requirements, a 2D interface for consumer’s multiple images was constructed. In a backward Kansei approach, designers could expect the outcome of consumers’ perceptions onto the redesigned or varying product forms. From changing the parameters, the system makes it possible for an efficient redesign for the profile of new mobile phone design.
28
Lu, Han-Chun, and 呂漢軍. "Some Integral Representations for the Products of Two Polynomials of the Certain Classes of Polynomials." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/99201916988807017659.
Full textAbstract:
博士淡江大學
數學學系博士班
100
We study the product of two different members of the associated family of the certain classes of polynomials. Our principal objective in this investigation is to investigate several general families of hypergeometric polynomials and their associated multiple integral representations. By suitably specializing our main results, the corresponding integral representations are deduced for familiar classes of hypergeometric polynomials. Also,each of the integral representations may be viewed also as a linearization relationship for the product of two different members of the associated family of hypergeometric polynomials.
29
Annapareddy, Tulasi Ram Reddy. "On Critical Points of Random Polynomials and Spectrum of Certain Products of Random Matrices." Thesis, 2015. http://etd.iisc.ernet.in/2005/3916.
Full textAbstract:
In the first part of this thesis, we study critical points of random polynomials. We choose two deterministic sequences of complex numbers, whose empirical measures converge to the same probability measure in complex plane. We make a sequence of polynomials whose zeros are chosen from either of sequences at random. We show that the limiting empirical measure of zeros and critical points agree for these polynomials. As a consequence we show that when we randomly perturb the zeros of a deterministic sequence of polynomials, the limiting empirical measures of zeros and critical points agree. This result can be interpreted as an extension of earlier results where randomness is reduced. Pemantle and Rivin initiated the study of critical points of random polynomials. Kabluchko proved the result considering the zeros to be i.i.d. random variables.
In the second part we deal with the spectrum of products of Ginibre matrices. Exact eigenvalue density is known for a very few matrix ensembles. For the known ones they often lead to determinantal point process. Let X1, X2,..., Xk be i.i.d Ginibre matrices of size n ×n whose entries are standard complex Gaussian random variables. We derive eigenvalue density for matrices of the form X1 ε1 X2 ε2 ... Xk εk , where εi = ±1 for i =1,2,..., k. We show that the eigenvalues form a determinantal point process. The case where k =2, ε1 +ε2 =0 was derived earlier by Krishnapur. In the case where
εi =1 for i =1,2,...,n was derived by Akemann and Burda. These two known cases can be obtained as special cases of our result.
30
Hattingh, Christiaan Johannes. "Sums and products of square-zero matrices." Diss., 2018. http://hdl.handle.net/10500/24519.
Full textAbstract:
Which matrices can be written as sums or products of square-zero matrices? This
question is the central premise of this dissertation. Over the past 25 years a signi -
cant body of research on products and linear combinations of square-zero matrices
has developed, and it is the aim of this study to present this body of research in a
consolidated, holistic format, that could serve as a theoretical introduction to the
subject.
The content of the research is presented in three parts: rst results within the
broader context of sums and products of nilpotent matrices are discussed, then
products of square-zero matrices, and nally sums of square-zero matrices.Mathematical Sciences
M. Sc. (Mathematics)
31
Węgrzycki, Karol. "Provably optimal dynamic programming." Doctoral thesis, 2021. https://depotuw.ceon.pl/handle/item/3869.
Full textAbstract:
In this thesis we study an application of dynamic programming technique to graph problems and approximation algorithms. We improve upon
state-of-the-art algorithms for All-Nodes Shortest Cycles, distance oracles, approximate algorithm for Partition, weak approximation for Subset Sum and others.
We also present equivalence classes for certain problems, that admit algorithms based on dynamic programming. Namely:
• (min, +)-convolution and knapsack problem,
• (min, max)-convolution and strongly polynomial approximate (min, max) - convolution,
• (min, max)-product and strongly polynomial approximate all-pairs shortest path.W rozprawie przedstawiamy nowe techniki analizy algorytmów opartych na programowaniu dynamicznym. Używamy ich do rozwiązywania problemów na grafach i przyśpieszeniu wybranych algorytmów aproksymacyjnych. Zaproponowane przez nas metody pozwalają na usprawnienie obecnie znanych algorytmów dla znajdywania najkrótszych cykli, wyroczni odległości, problemów aproksymacyjnych związanych z problemem plecakowym i innych. W rozprawie proponujemy także klasy równoważności dla wybranych problemów, które mają efektywne algorytmy oparte na programowaniu dynamicznym. W szczególności: • (min, +)-konwolucji i problemu plecakowego, • (min, max)-konwolucji i silnie wielomianowej aproksymacji dla (min, +)-konwolucji, • (min, max)-produktu i silnie wielomianowej aproksymacji dla znajdywania najkrótszych ścieżek w grafie.