京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19123号 / 情博第569号 / 新制||情||100(附属図書館) / 32074 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 中村 佳正, 教授 田中 利幸 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

This thesis is on the numerical computation of eigenvalues of symmetric hierarchical matrices. The numerical algorithms used for this computation are derivations of the LR Cholesky algorithm, the preconditioned inverse iteration, and a bisection method based on LDLT factorizations. The investigation of QR decompositions for H-matrices leads to a new QR decomposition. It has some properties that are superior to the existing ones, which is shown by experiments using the HQR decompositions to build a QR (eigenvalue) algorithm for H-matrices does not progress to a more efficient algorithm than the LR Cholesky algorithm. The implementation of the LR Cholesky algorithm for hierarchical matrices together with deflation and shift strategies yields an algorithm that require O(n) iterations to find all eigenvalues. Unfortunately, the local ranks of the iterates show a strong growth in the first steps. These H-fill-ins makes the computation expensive, so that O(n³) flops and O(n²) storage are required. Theorem 4.3.1 explains this behavior and shows that the LR Cholesky algorithm is efficient for the simple structured Hl-matrices. There is an exact LDLT factorization for Hl-matrices and an approximate LDLT factorization for H-matrices in linear-polylogarithmic complexity. This factorizations can be used to compute the inertia of an H-matrix. With the knowledge of the inertia for arbitrary shifts, one can compute an eigenvalue by bisectioning. The slicing the spectrum algorithm can compute all eigenvalues of an Hl-matrix in linear-polylogarithmic complexity. A single eigenvalue can be computed in O(k²n log^4 n). Since the LDLT factorization for general H-matrices is only approximative, the accuracy of the LDLT slicing algorithm is limited. The local ranks of the LDLT factorization for indefinite matrices are generally unknown, so that there is no statement on the complexity of the algorithm besides the numerical results in Table 5.7. The preconditioned inverse iteration computes the smallest eigenvalue and the corresponding eigenvector. This method is efficient, since the number of iterations is independent of the matrix dimension. If other eigenvalues than the smallest are searched, then preconditioned inverse iteration can not be simply applied to the shifted matrix, since positive definiteness is necessary. The squared and shifted matrix (M-mu I)² is positive definite. Inner eigenvalues can be computed by the combination of folded spectrum method and PINVIT. Numerical experiments show that the approximate inversion of (M-mu I)² is more expensive than the approximate inversion of M, so that the computation of the inner eigenvalues is more expensive. We compare the different eigenvalue algorithms. The preconditioned inverse iteration for hierarchical matrices is better than the LDLT slicing algorithm for the computation of the smallest eigenvalues, especially if the inverse is already available. The computation of inner eigenvalues with the folded spectrum method and preconditioned inverse iteration is more expensive. The LDLT slicing algorithm is competitive to H-PINVIT for the computation of inner eigenvalues. In the case of large, sparse matrices, specially tailored algorithms for sparse matrices, like the MATLAB function eigs, are more efficient. If one wants to compute all eigenvalues, then the LDLT slicing algorithm seems to be better than the LR Cholesky algorithm. If the matrix is small enough to be handled in dense arithmetic (and is not an Hl(1)-matrix), then dense eigensolvers, like the LAPACK function dsyev, are superior. The H-PINVIT and the LDLT slicing algorithm require only an almost linear amount of storage. They can handle larger matrices than eigenvalue algorithms for dense matrices. For Hl-matrices of local rank 1, the LDLT slicing algorithm and the LR Cholesky algorithm need almost the same time for the computation of all eigenvalues. For large matrices, both algorithms are faster than the dense LAPACK function dsyev.

This thesis is on the numerical computation of eigenvalues of symmetric hierarchical matrices. The numerical algorithms used for this computation are derivations of the LR Cholesky algorithm, the preconditioned inverse iteration, and a bisection method based on LDLT factorizations. The investigation of QR decompositions for H-matrices leads to a new QR decomposition. It has some properties that are superior to the existing ones, which is shown by experiments using the HQR decompositions to build a QR (eigenvalue) algorithm for H-matrices does not progress to a more efficient algorithm than the LR Cholesky algorithm. The implementation of the LR Cholesky algorithm for hierarchical matrices together with deflation and shift strategies yields an algorithm that require O(n) iterations to find all eigenvalues. Unfortunately, the local ranks of the iterates show a strong growth in the first steps. These H-fill-ins makes the computation expensive, so that O(n³) flops and O(n²) storage are required. Theorem 4.3.1 explains this behavior and shows that the LR Cholesky algorithm is efficient for the simple structured Hl-matrices. There is an exact LDLT factorization for Hl-matrices and an approximate LDLT factorization for H-matrices in linear-polylogarithmic complexity. This factorizations can be used to compute the inertia of an H-matrix. With the knowledge of the inertia for arbitrary shifts, one can compute an eigenvalue by bisectioning. The slicing the spectrum algorithm can compute all eigenvalues of an Hl-matrix in linear-polylogarithmic complexity. A single eigenvalue can be computed in O(k²n log^4 n). Since the LDLT factorization for general H-matrices is only approximative, the accuracy of the LDLT slicing algorithm is limited. The local ranks of the LDLT factorization for indefinite matrices are generally unknown, so that there is no statement on the complexity of the algorithm besides the numerical results in Table 5.7. The preconditioned inverse iteration computes the smallest eigenvalue and the corresponding eigenvector. This method is efficient, since the number of iterations is independent of the matrix dimension. If other eigenvalues than the smallest are searched, then preconditioned inverse iteration can not be simply applied to the shifted matrix, since positive definiteness is necessary. The squared and shifted matrix (M-mu I)² is positive definite. Inner eigenvalues can be computed by the combination of folded spectrum method and PINVIT. Numerical experiments show that the approximate inversion of (M-mu I)² is more expensive than the approximate inversion of M, so that the computation of the inner eigenvalues is more expensive. We compare the different eigenvalue algorithms. The preconditioned inverse iteration for hierarchical matrices is better than the LDLT slicing algorithm for the computation of the smallest eigenvalues, especially if the inverse is already available. The computation of inner eigenvalues with the folded spectrum method and preconditioned inverse iteration is more expensive. The LDLT slicing algorithm is competitive to H-PINVIT for the computation of inner eigenvalues. In the case of large, sparse matrices, specially tailored algorithms for sparse matrices, like the MATLAB function eigs, are more efficient. If one wants to compute all eigenvalues, then the LDLT slicing algorithm seems to be better than the LR Cholesky algorithm. If the matrix is small enough to be handled in dense arithmetic (and is not an Hl(1)-matrix), then dense eigensolvers, like the LAPACK function dsyev, are superior. The H-PINVIT and the LDLT slicing algorithm require only an almost linear amount of storage. They can handle larger matrices than eigenvalue algorithms for dense matrices. For Hl-matrices of local rank 1, the LDLT slicing algorithm and the LR Cholesky algorithm need almost the same time for the computation of all eigenvalues. For large matrices, both algorithms are faster than the dense LAPACK function dsyev.:List of Figures xi List of Tables xiii List of Algorithms xv List of Acronyms xvii List of Symbols xix Publications xxi 1 Introduction 1 1.1 Notation 2 1.2 Structure of this Thesis 3 2 Basics 5 2.1 Linear Algebra and Eigenvalues 6 2.1.1 The Eigenvalue Problem 7 2.1.2 Dense Matrix Algorithms 9 2.2 Integral Operators and Integral Equations 14 2.2.1 Definitions 14 2.2.2 Example - BEM 16 2.3 Introduction to Hierarchical Arithmetic 17 2.3.1 Main Idea 17 2.3.2 Definitions 19 2.3.3 Hierarchical Arithmetic 24 2.3.4 Simple Hierarchical Matrices (Hl-Matrices) 30 2.4 Examples 33 2.4.1 FEM Example 33 2.4.2 BEM Example 36 2.4.3 Randomly Generated Examples 37 2.4.4 Application Based Examples 38 2.4.5 One-Dimensional Integral Equation 38 2.5 Related Matrix Formats 39 2.5.1 H2-Matrices 40 2.5.2 Diagonal plus Semiseparable Matrices 40 2.5.3 Hierarchically Semiseparable Matrices 42 2.6 Review of Existing Eigenvalue Algorithms 44 2.6.1 Projection Method 44 2.6.2 Divide-and-Conquer for Hl(1)-Matrices 45 2.6.3 Transforming Hierarchical into Semiseparable Matrices 46 2.7 Compute Cluster Otto 47 3 QR Decomposition of Hierarchical Matrices 49 3.1 Introduction 49 3.2 Review of Known QR Decompositions for H-Matrices 50 3.2.1 Lintner’s H-QR Decomposition 50 3.2.2 Bebendorf’s H-QR Decomposition 52 3.3 A new Method for Computing the H-QR Decomposition 54 3.3.1 Leaf Block-Column 54 3.3.2 Non-Leaf Block Column 56 3.3.3 Complexity 57 3.3.4 Orthogonality 60 3.3.5 Comparison to QR Decompositions for Sparse Matrices 61 3.4 Numerical Results 62 3.4.1 Lintner’s H-QR decomposition 62 3.4.2 Bebendorf’s H-QR decomposition 66 3.4.3 The new H-QR decomposition 66 3.5 Conclusions 67 4 QR-like Algorithms for Hierarchical Matrices 69 4.1 Introduction 70 4.1.1 LR Cholesky Algorithm 70 4.1.2 QR Algorithm 70 4.1.3 Complexity 71 4.2 LR Cholesky Algorithm for Hierarchical Matrices 72 4.2.1 Algorithm 72 4.2.2 Shift Strategy 72 4.2.3 Deflation 73 4.2.4 Numerical Results 73 4.3 LR Cholesky Algorithm for Diagonal plus Semiseparable Matrices 75 4.3.1 Theorem 75 4.3.2 Application to Tridiagonal and Band Matrices 79 4.3.3 Application to Matrices with Rank Structure 79 4.3.4 Application to H-Matrices 80 4.3.5 Application to Hl-Matrices 82 4.3.6 Application to H2-Matrices 83 4.4 Numerical Examples 84 4.5 The Unsymmetric Case 84 4.6 Conclusions 88 5 Slicing the Spectrum of Hierarchical Matrices 89 5.1 Introduction 89 5.2 Slicing the Spectrum by LDLT Factorization 91 5.2.1 The Function nu(M − µI) 91 5.2.2 LDLT Factorization of Hl-Matrices 92 5.2.3 Start-Interval [a, b] 96 5.2.4 Complexity 96 5.3 Numerical Results 97 5.4 Possible Extensions 100 5.4.1 LDLT Slicing Algorithm for HSS Matrices 103 5.4.2 LDLT Slicing Algorithm for H-Matrices 103 5.4.3 Parallelization 105 5.4.4 Eigenvectors 107 5.5 Conclusions 107 6 Computing Eigenvalues by Vector Iterations 109 6.1 Power Iteration 109 6.1.1 Power Iteration for Hierarchical Matrices 110 6.1.2 Inverse Iteration 111 6.2 Preconditioned Inverse Iteration for Hierarchical Matrices 111 6.2.1 Preconditioned Inverse Iteration 113 6.2.2 The Approximate Inverse of an H-Matrix 115 6.2.3 The Approximate Cholesky Decomposition of an H-Matrix 116 6.2.4 PINVIT for H-Matrices 117 6.2.5 The Interior of the Spectrum 120 6.2.6 Numerical Results 123 6.2.7 Conclusions 130 7 Comparison of the Algorithms and Numerical Results 133 7.1 Theoretical Comparison 133 7.2 Numerical Comparison 135 8 Conclusions 141 Theses 143 Bibliography 145 Index 153

Distributed optimization over multi-agent networks has become an increasingly popular research topic as it incorporates many applications from various areas such as consensus optimization, distributed control, network resource allocation, large scale machine learning, etc. Parallel distributed solution algorithms are highly desirable as they are more scalable, more robust against agent failure, align more naturally with either underlying agent network topology or big-data parallel computing framework. In this dissertation, we consider a multi-agent optimization formulation where the global objective function is the summation of individual local objective functions with respect to local agents' decision variables of different dimensions, and the constraints include both local private constraints and shared coupling constraints. Employing and extending tools from the monotone operator theory (including resolvent operator, operator splitting, etc.) and fixed point iteration of nonexpansive, averaged operators, a series of distributed solution approaches are proposed, which are all iterative algorithms that rely on parallel agent level local updates and inter-agent coordination. Some of the algorithms require synchronizations across all agents for information exchange during each iteration while others allow asynchrony and delays. The algorithms' convergence to an optimal solution if one exists are established by first characterizing them as fixed point iterations of certain averaged operators under certain carefully designed norms, then showing that the fixed point sets of these averaged operators are exactly the optimal solution set of the original multi-agent optimization problem. The effectiveness and performances of the proposed algorithms are demonstrated and compared through several numerical examples.<br>

La modélisation des équilibres thermodynamiques entre phases est essentielle pour le génie des procédés et le génie pétrolier. L’analyse de la stabilité des phases est un problème de la plus haute importance parmi les calculs d’équilibre des phases. Le calcul de stabilité décide si un système se présente dans un état monophasique ou multiphasique ; si le système se sépare en deux ou plusieurs phases, les résultats du calcul de stabilité fournissent une initialisation de qualité pour les calculs de flash (Michelsen, 1982b), et permettent la validation des résultats des calculs de flash multiphasique. Le problème de la stabilité des phases est résolu par une minimisation sans contraintes de la fonction distance au plan tangent à la surface de l’énergie libre de Gibbs (« tangent plane distance », ou TPD). Une phase est considérée comme étant thermodynamiquement stable si la fonction TPD est non- négative pour tous les points stationnaires, tandis qu’une valeur négative indique une phase thermodynamiquement instable. La surface TPD dans l’espace compositionnel est non- convexe et peut être hautement non linéaire, ce qui fait que les calculs de stabilité peuvent être extrêmement difficiles pour certaines conditions, notamment aux voisinages des singularités. On distingue deux types de singularités : (i) au lieu de la limite du test de stabilité (stability test limit locus, ou STLL), et ii) à la spinodale (la limite intrinsèque de la stabilité thermodynamique). Du point de vue géométrique, la surface TPD présente un point selle, correspondant à une solution non triviale (à la STLL) ou triviale (à la spinodale). Dans le voisinage de ces singularités, le nombre d’itérations de toute méthode de minimisation augmente dramatiquement et la divergence peut survenir. Cet inconvénient est bien plus sévère pour la STLL que pour la spinodale. Le présent mémoire est structuré sur trois grandes lignes : (i) après la présentation du critère du plan tangent à la surface de l’énergie libre de Gibbs, plusieurs solutions itératives (gradient et méthodes d’accélération de la convergence, méthodes de second ordre de Newton et méthodes quasi- Newton), du problème de la stabilité des phases sont présentées et analysées, surtout du point de vue de leurs comportement près des singularités; (ii) Suivant l’analyse des valeurs propres, du conditionnement de la matrice Hessienne et de l’échelle du problème, ainsi que la représentation de la surface de la fonction TPD, la résolution du calcul de la stabilité des phases par la minimisation des fonctions coût modifiées est adoptée. Ces fonctions « coût » sont choisies de telle sorte que tout point stationnaire (y compris les points selle) de la fonction TPD soit converti en minimum global; la Hessienne à la STLL est dans ce cas positif définie, et non indéfinie, ce qui mène a une amélioration des propriétés de convergence, comme montré par plusieurs exemples pour des mélanges représentatifs, synthétiques et naturels. Finalement, (iii) les calculs de stabilité sont menés par une méthode d’optimisation globale, dite de Tunneling. La méthode de Tunneling consiste à détruire (en plaçant un pôle) les minima déjà trouvés par une méthode de minimisation locale, et a tunneliser pour trouver un point situé dans une autre vallée de la surface de la fonction coût qui contient un minimum 9 à une valeur plus petite de la fonction coût; le processus continue jusqu'à ce que les critères du minimum global soient remplis. Plusieurs exemples soigneusement choisis montrent la robustesse et l’efficacité de la méthode de Tunneling pour la minimisation de la fonction TPD, ainsi que pour la minimisation des fonctions coût modifiées. / The thermodynamic phase equilibrium modelling is an essential issue for petroleum and process engineering. Phase stability analysis is a highly important problem among phase equilibrium calculations. The stability computation establishes whether a given mixture is in one or several phases. If a mixture splits into two or more phases, the stability calculations provide valuables initialisation sets for the flash calculations, and allow the validation of multiphase flash calculations. The phase stability problem is solved as an unconstrained minimisation of the tangent plan distance (TPD) function to the Gibbs free energy surface. A phase is thermodynamically stable if the TPD function is non-negative at all its stationary points, while a negative value indicates an unstable case. The TPD surface is non-convex and may be highly non-linear in the compositional space; for this reason, phase stability calculation may be extremely difficult for certain conditions, mainly within the vicinity of singularities. One can distinguish two types of singularities: (i) the stability test limit locus (STLL), and (ii) the intrinsic limit of stability (spinodal). Geometrically, the TPD surface exhibits a saddle point, corresponding to a non-trivial (at the STLL) or trivial solution (at the spinodal). In the immediate vicinity of these singularities, the number of iterations of all minimisation methods increases dramatically, and divergence could occur. This inconvenient is more severe for the STLL than for the spinodal. The work presented herein is structured as follow: (i) after the introduction to the concept of tangent plan distance to the Gibbs free energy surface, several iterative methods (gradient, acceleration methods, second-order Newton and quasi-Newton) are presented, and their behaviour analysed, especially near singularities. (ii) following the analysis of Hessian matrix eigenvalues and conditioning, of problem scaling, as well as of the TPD surface representation, the solution of phase stability computation using modified objective functions is adopted. The latter are chosen in such a manner that any stationary point of the TPD function becomes a global minimum of the modified function; at the STLL, the Hessian matrix is no more indefinite, but positive definite. This leads to a better scheme of convergence as will be shown in various examples for synthetic and naturally occurring mixtures. Finally, (iii) the so-called Tunneling global optimization method is used for the stability analysis. This method consists in destroying the minima already found (by placing poles), and to tunnel to another valley of the modified objective function to find a new minimum with a smaller value of the objective function. The process is resumed when criteria for the global minimum are fulfilled. Several carefully chosen examples demonstrate the robustness and the efficiency of the Tunneling method to minimize the TPD function, as well as the modified objective functions.

Die vorliegende Arbeit beschäftigt sich mit verschiedenen Aspekten der Finanzmathematik. Ein erweitertes Libor Markt Modell wird betrachtet, welches genug Flexibilität bietet, um akkurat an Caplets und Swaptions zu kalibrieren. Weiterhin wird die Bewertung komplexerer Finanzderivate, zum Beispiel durch Simulation, behandelt. In hohen Dimensionen können solche Simulationen sehr zeitaufwendig sein. Es werden mögliche Verbesserungen bezüglich der Komplexität aufgezeigt, z.B. durch Faktorreduktion. Zusätzlich wird das sogenannte Andersen-Simulationsschema von einer auf mehrere Dimensionen erweitert, wobei das Konzept des „Momentmatchings“ zur Approximation des Volaprozesses in einem Heston Modell genutzt wird. Die daraus resultierende verbesserten Konvergenz des Gesamtprozesses führt zu einer verringerten Komplexität. Des Weiteren wird die Bewertung Amerikanischer Optionen als optimales Stoppproblem betrachtet. In höheren Dimensionen ist die simulationsbasierte Bewertung meist die einzig praktikable Lösung, da diese eine dimensionsunabhängige Konvergenz gewährleistet. Eine neue Methode der Varianzreduktion, die Multilevel-Idee, wird hier angewandt. Es wird eine untere Preisschranke unter zu Hilfenahme der Methode der „policy iteration“ hergeleitet. Dafür werden Konvergenzraten für die Simulation des Optionspreises erarbeitet und eine detaillierte Komplexitätsanalyse dargestellt. Abschließend wird das Preisen von Amerikanischen Optionen unter Modellunsicherheit behandelt, wodurch die Restriktion, nur ein bestimmtes Wahrscheinlichkeitsmodell zu betrachten, entfällt. Verschiedene Modelle können plausibel sein und zu verschiedenen Optionswerten führen. Dieser Ansatz führt zu einem nichtlinearen, verallgemeinerten Erwartungsfunktional. Mit Hilfe einer verallgemeinerte Snell''sche Einhüllende wird das Bellman Prinzip hergeleitet. Dadurch kann eine Lösung durch Rückwärtsrekursion erhalten werden. Ein numerischer Algorithmus liefert untere und obere Preisschranken. / The work presented here deals with several aspects of financial mathematics. An extended Libor market model is considered offering enough flexibility to accurately calibrate to various market data for caplets and swaptions. Moreover the evaluation of more complex financial derivatives is considered, for instance by simulation. In high dimension such simulations can be very time consuming. Possible improvements regarding the complexity of the simulation are shown, e.g. factor reduction. In addition the well known Andersen simulation scheme is extended from one to multiple dimensions using the concept of moment matching for the approximation of the vola process in a Heston model. This results in an improved convergence of the whole process thus yielding a reduced complexity. Further the problem of evaluating so called American options as optimal stopping problem is considered. For an efficient evaluation of these options, particularly in high dimensions, a simulation based approach offering dimension independent convergence often happens to be the only practicable solution. A new method of variance reduction given by the multilevel idea is applied to this approach. A lower bound for the option price is obtained using “multilevel policy iteration” method. Convergence rates for the simulation of the option price are obtained and a detailed complexity analysis is presented. Finally the valuation of American options under model uncertainty is examined. This lifts the restriction of considering one particular probabilistic model only. Different models might be plausible and may lead to different option values. This approach leads to a non-linear expectation functional, calling for a generalization of the standard expectation case. A generalized Snell envelope is obtained, enabling a backward recursion via Bellman principle. A numerical algorithm to valuate American options under ambiguity provides lower and upper price bounds.

The pseudospin symmetry concept is investigated by solving the Dirac equation for the exactly solvable potentials such as pseudoharmonic potential, Mie-type potential, Woods-Saxon potential and Hulth&eacute / n plus ring-shaped potential with any spin-orbit coupling term $kappa$. Nikiforov-Uvarov Method, Asymptotic Iteration Method and functional analysis method are used in the calculations. The energy eigenvalue equations of the Dirac particles are found and the corresponding radial wave functions are presented in terms of special functions. We look for the contribution of the ring-shaped potential to the energy spectra of the Dirac particles. Particular cases of the potentials are also discussed. By considering some particular cases, our results are reduced to the well-known ones presented in the literature. In addition, by taking equal mixture of scalar and vector potentials together with tensor potential, solutions of the Dirac equation are found and then the energy splitting between the two states in the pseudospin doublets is investigated. We indicate that degeneracy between members of pseudospin doublet is removed by tensor interactions. Effects of the potential parameters on the pseudospin doublet splitting are also studied. Radial nodes structure of the Dirac spinor are presented.

We present a new method for the computation of low rank approximations to the solution of large, sparse, stable Lyapunov equations. It is based on a generalization of the classical Smith method and profits by the usual low rank property of the right hand side matrix. The requirements of the method are moderate with respect to both computational cost and memory. Hence, it provides a possibility to tackle large scale control problems. Besides the efficient solution of the matrix equation itself, a thorough integration of the method into several control algorithms can improve their performance to a high degree. This is demonstrated for algorithms for model reduction and optimal control. Furthermore, we propose a heuristic for determining a set of suboptimal ADI shift parameters. This heuristic, which is based on a pair of Arnoldi processes, does not require any a priori knowledge on the spectrum of the coefficient matrix of the Lyapunov equation. Numerical experiments show the efficiency of the iterative scheme combined with the heuristic for the ADI parameters.

Abstract Fading in wireless channels, the limited battery energy available in wireless handsets, the changing user demands and the increasing demand for high data rate and low delay pose serious design challenges in the future generations of mobile communication systems. It is necessary to develop efficient transmission policies that adapt to changes in network conditions and achieve the target delay and rate with minimum power consumption. In this thesis, a number of new paradigms in wireless networks are presented. Dynamic programming tools are used to provide dynamic network stabilizing resource allocation solutions for virtualized data centers with clouds, cooperative networks and heterogeneous networks. Exact dynamic programming is used to develop optimal resource allocation and topology control policies for these networks with queues and time varying channels. In addition, approximate dynamic programming is also considered to provide new sub-optimal solutions. Unified system models and unified control problems are also provided for both secondary service provider and primary service provider cognitive networks and for conventional wireless networks. The results show that by adapting to the changes in queue lengths and channel states, the dynamic policy mitigates the effects of primary service provider and secondary service provider cognitive networks on each other. We investigate the network stability and provide new unified stability regions for primary service provider and secondary service provider cognitive networks as well as for conventional wireless networks. The K-step Lyapunov drift is used to analyse the performance and stability of the proposed dynamic control policies, and new unified stability analysis and queuing bound are provided for both primary service provider and secondary service provider cognitive networks and for conventional wireless networks. By adapting to the changes in network conditions, the dynamic control policies are shown to stabilize the network and to minimize the bound for the average queue length. In addition, we prove that the previously proposed frame based does not minimize the bound for the average delay, when there are shared resources between the terminals with queues. / Tiivistelmä Langattomien kanavien häipyminen, langattomien laitteiden akkujen rajallinen koko, käyttäjien käyttötarpeiden muutokset sekä lisääntyvän tiedonsiirron ja lyhyemmän viiveen vaatimukset luovat suuria haasteita tulevaisuuden langattomien verkkojen suunnitteluun. On välttämätöntä kehittää tehokkaita resurssien allokointialgoritmeja, jotka sopeutuvat verkkojen muutoksiin ja saavuttavat sekä tavoiteviiveen että tavoitedatanopeuden mahdollisimman pienellä tehon kulutuksella. Tässä väitöskirjassa esitetään uusia paradigmoja langattomille tietoliikenneverkoille. Dynaamisen ohjelmoinnin välineitä käytetään luomaan dynaamisia verkon stabiloivia resurssien allokointiratkaisuja virtuaalisille pilvipalveludatakeskuksille, käyttäjien yhteistyöverkoille ja heterogeenisille verkoille. Tarkkoja dynaamisen ohjelmoinnin välineitä käytetään kehittämään optimaalisia resurssien allokointi ja topologian kontrollointialgoritmeja näille jonojen ja häipyvien kanavien verkoille. Tämän lisäksi, estimoituja dynaamisen ohjelmoinnin välineitä käytetään luomaan uusia alioptimaalisia ratkaisuja. Yhtenäisiä systeemimalleja ja yhtenäisiä kontrollointiongelmia luodaan sekä toissijaisen ja ensisijaisen palvelun tuottajan kognitiivisille verkoille että tavallisille langattomille verkoille. Tulokset osoittavat että sopeutumalla jonojen pituuksien ja kanavien muutoksiin dynaaminen tekniikka vaimentaa ensisijaisen ja toissijaisen palvelun tuottajien kognitiivisten verkkojen vaikutusta toisiinsa. Tutkimme myös verkon stabiiliutta ja luomme uusia stabiilisuusalueita sekä ensisijaisen ja toissijaisen palveluntuottajan kognitiivisille verkoille että tavallisille langattomille verkoille. K:n askeleen Lyapunovin driftiä käytetään analysoimaan dynaamisen kontrollointitekniikan suorituskykyä ja stabiiliutta. Lisäksi uusi yhtenäinen stabiiliusanalyysi ja jonon yläraja luodaan ensisijaisen ja toissijaisen palveluntuottajan kognitiivisille verkoille ja tavallisille langattomille verkoille. Dynaamisen algoritmin näytetään stabiloivan verkko ja minimoivan keskimääräisen jonon pituuden yläraja sopeutumalla verkon olosuhteiden muutoksiin. Tämän lisäksi todistamme että aiemmin esitetty frame-algoritmi ei minimoi keskimääräisen viiveen ylärajaa, kun käyttäjät jakavat keskenään resursseja.

The thesis is focused on software development process and its products from initial designs through the way of implementation until final delivery to customer. The thesis brings up some basic facts about software engineering with further detailed description of one of its parts, the modern models of software life cycles with focus on the agile life cycle because of its significant benefits and effective implementation. This model is represented by Agile Model Driven Development which has been submitted not only theoretically but in practice. Finally, there is also a short description of Unified Modeling Language which is used as a modeling language.