Search

The growing interest in computing structured matrix functions stems from the fact that preserving and exploiting the structure of matrices can help us gain physically meaningful solutions with less computational cost and memory requirement. The work presented here is divided into two parts. The first part deals with the computation of functions of structured matrices. The second part is concerned with the structured error analysis in the computation of matrix functions. We present algorithms applying the inverse scaling and squaring method and using the Schur-like form of the symplectic matrices as an alternative to the algorithms using the Schur decomposition to compute the logarithm of symplectic matrices. There are two main calculations in the inverse scaling and squaring method: taking a square root and evaluating the Padé approximants. Numerical experiments suggest that using the Schur-like form with the structure preserving iterations for the square root helps us to exploit the Hamiltonian structure of the logarithm of symplectic matrices. Some type of matrices are nearly structured. We discuss the conditions for using the nearest structured matrix to the nearly structured one by analysing the forward error bounds. Since the structure preserving algorithms for computing the functions of matrices provide advantages in terms of accuracy and data storage we suggest to compute the function of the nearest structured matrix. The analysis is applied to the nearly unitary, nearly Hermitian and nearly positive semi-definite matrices for the matrix logarithm, square root, exponential, cosine and sine functions. It is significant to investigate the effect of the structured perturbations in the sensitivity analysis of matrix functions. We study the structured condition number of matrix functions defined between smooth square matrix manifolds. We develop algorithms computing and estimating the structured condition number. We also present the lower and upper bounds on the structured condition number, which are cheaper to compute than the "exact" structured condition number. We observe that the lower bounds give a good estimation for the structured condition numbers. Comparing the structured and unstructured condition number reveals that they can differ by several orders of magnitude. Having discussed how to compute the structured condition number of matrix functions defined between smooth square matrix manifolds we apply the theory of structured condition numbers to the structured matrix factorizations. We measure the sensitivity of matrix factors to the structured perturbations for the structured polar decomposition, structured sign factorization and the generalized polar decomposition. Finally, we consider the unstructured perturbation analysis for the canonical generalized polar decomposition by using three different methods. Apart from theoretical aspect of the perturbation analysis, perturbation bounds obtained from these methods are compared numerically and our findings show an improvement on the sharpness of the perturbation bounds in the literature.

The kangaroo method for the Pollard's rho algorithm provides a powerful way to solve discrete log problems. There exist parameters for it that allow it to be optimized in such a way as to prevent what are known as "useless collisions" in exchange for the limitation that the number of parallel resources used must be both finite and known ahead of time. This thesis puts forward an analysis of the situation and examines the potential acceleration that can be gained through the use of parallel resources beyond those initially utilized by an algorithm so configured. In brief, the goal in doing this is to reconcile the rapid rate of increase in parallel processing capabilities present in consumer level hardware with the still largely sequential nature of a large portion of the algorithms used in the software that is run on that hardware. The core concept, then, would be to allow "spare" parallel resources to be utilized in an advanced sort of guess-and-check to potentially produce occasional speedups whenever, for lack of a better way to put it, those guesses are correct. The methods presented in this thesis are done so with an eye towards expanding and reapplying them to this broadly expressed problem, however herein the discrete log problem has been chosen to be utilized as a suitable example of how such an application can proceed. This is primarily due to the observation that Pollard's parameters for the avoidance of so-called "useless collisions" generated from the kangaroo method of solving said problem are restrictive in the number of kangaroos used at any given time. The more relevant of these restrictions to this point is the fact that they require the total number of kangaroos to be odd. Most consumer-level hardware which provides more than a single computational core provides an even number of such cores, so as a result it is likely the utilization of such hardware for this purpose will leave one or more cores idle. While these idle compute cores could also potentially be utilized for other tasks given that we are expressly operating in the context of consumer-level hardware, such considerations are largely outside the scope of this thesis. Besides, with the rate of change consumer computational hardware and software environments have historically changed it seems to be more useful to address the topic on a more purely algorithmic level; at the very least, it is more efficient as less effort needs to be expended future-proofing this thesis against future changes to its context than might have otherwise been necessary.

This paper outlines the evolution of the logarithm from the days of Archimedes to the logarithm now used in modern mathematics. Each type of logarithm developed had its particular usefulness. The Archimedean logarithm helped astronomers by drastically shortening the time it took to multiply large numbers, while Napier’s logarithm could be used as a tool to solve velocity problems. With the discovery of the number e, the natural logarithm was developed. Due to the frequent use of e, many of the properties of logarithms were defined to work nicely for the natural logarithm to make calculations easier. This paper will explain the proofs and connections of such properties in a way that could be presented in a calculus class.