Faculty of Science

Permanent URI for this communityhttps://hdl.handle.net/10294/147

The Faculty of Science represents one of the strongest academic areas at the University of Regina. It attracts more than half of all external research funding and holds two Canada Research Chairs. With the need for scientific and technical skills in the 21st century, students will find that the strengths of the Faculty make it an attractive one in which to further their education.

The Faculty is composed of six departments:

For more information on the Faculty of Science and its programs, please visit the web site at www.uregina.ca/science/

Browse

Now showing 1 - 20 of 148

Open Access
Approximation and Visualization of Sets Defined by Iterated Function Systems
(University of Regina, 1991-03) Hepting, Daryl H.
An iterated function system (IFS) is defined to be a set of contractive affine transformations. When iterated, these transformations define a closed set, called the attractor of an IFS, which has fractal characteristics. Fractals of any sort are currently a topic of great popular appeal, largely due to the exciting images to which they lend themselves. Iterated function systems represent one of the newest sources of fractal images. Research to date has focused on exploiting IFS techniques for the generation of fractals and for use in modelling applications. Both areas of this research are well suited to computer graphics, and this thesis examine the IFS techniques from a computer graphics perspective. As a source of fractals, iterated function systems have some relationship to other methods of fractal generation. In particular, the relationship between IFS attractors and Julia sets will be examined throughout the thesis. Many insights can be gained from the previous work done by Peitgen, Richter and Saupe [32, 33] both in terms of methods for the generation of the fractal sets and methods for their visualization. The differences between the linear transformations which compose an IFS and the quadratic polynomials which define Julia sets are significant, but not moreso than their similarities. This thesis deals with the related questions of approximation and visualization. The method of constructing the approximating set of points is dependent upon the visualization method in use. Methods have been developed both to visualize the attractor and its complement. The two techniques used to examine the complement set are based on the distance and escape-time functions. The modelling power of standard IFS techniques is limited in that they cannot be used to model any object which is not strictly self-affine. To combat this, methods for controlling transformation application are examined which allow objects without strict self-affinity to be modelled. As part of this research, an extensible software system was developed to allow experimentation with the various concepts discussed. A description of that system is included in Chapter 6.
Open Access
Rendering Methods for Iterated Function Systems
(North-Holland, 1991-12) Hepting, Daryl; Prusinkiewicz, Przemyslaw; Saupe, Dietmar
This paper describes rendering methods for iterated function systems (IFS’s). The rendering process consists of the generation of a field of data using an IFS and its visualization by means of computer graphics. Two groups of methods are presented: 1. Rendering of the attractor A of an IFS. These attracting methods may visualize the geometry and additionally the invariant measure supported by the attractor. 2. Rendering the complement of the attractor. There are three approaches, namely methods representing Euclidean distance from A; repelling methods, computing the escape time of a point from A, and methods using (electrostatic) potential functions of the attractor. The last of these methods calculates integrals with respect to the invariant measure of the attractor. An algorithm which generates an approximation of such integrals with prescribed tolerance is presented. This provides an alternative to the usual approach based on Elton's ergodic theorem and time average of trajectories generated by the “chaos game", where no error bound is available. Algorithms specifying the details of all methods are presented, some of them in the form of pseudocode. Examples of images obtained using these algorithms are given. The relationship to previously developed methods for visualizing Mandelbrot and Julia sets is also discussed.
Open Access
The Escape Buffer: Efficient Computation of Escape Time for Linear Fractals
(Canadian Human Computer Communications Society, 1995-05-17) Hepting, Daryl; Hart, John
The study of linear fractals has gained a great deal from the study of quadratic fractals, despite important differences. Methods for classifying points in the complement of a fractal shape were originally developed for quadratic fractals, to provide insight into their underlying dynamics. These methods were later modified for use with linear fractals. This paper reconsiders one such classification, called escape time, and presents a new algorithm for its computation that is significantly faster and conceptually simpler. Previous methods worked backwards, by mapping pixels into classified regions, whereas the new forward algorithm uses an "escape buffer" to map classified regions onto pixels. The efficiency of the escape buffer is justified by a careful analysis of its performance on linear fractals with various properties.
Open Access
Post-magmatic alteration in eudialyte from the North Qoroq centre, South Greenland
(Mineralogical Society of Great Britian, 1997-02) Coulson, Ian Michael
The North Qoroq centre comprises a series of nested nepheline syenite intrusions and forms part of the midlate Proterozoic Gardar province of South Greenland. Within the centre fractionation has produced varied rock types ranging from augite-syenite to lujavrite, a eudialyte microsyenite. Samples of eudialyte from the lujavrites of unit SN1B of the centre show evidence for two-stage alteration. This alteration ranges from slight modification along crystal margins to complete breakdown and replacement by new pseudomorphing phases. Modification to crystal margins is accompanied by increasing Nb and Zr contents and is related to metasomatism produced by the intrusion of younger syenite units of the North Qoroq centre. More extensive alteration is as a result of metasomatism followed by lower-temperature supergene alteration. Simplified reactions for this breakdown include eudialyte + metasomatic fluid = allanite + nepheline; eudialyte + metasomatic fluid = titanite + aegirine + mesandrite + w6hlerite; eudialyte + fluid = zirfesite + fluid. Mass balance calculations for altered compared with unaltered samples of lujavrite show that alteration took place at approximately constant volume with an overall increase in Fe (+2.41 g/100g), Si and K (+0.65 and +0.61 g/ 100g), whilst Na (-2.67 g/100g) and all trace elements, particularly La, Y, Nb and Zr (-5.6 to -166 g/ 10000g) are lost from the system.
Open Access
Faculty of Science annual report, January 1, 2004 - December 31, 2004
(Faculty of Science, University of Regina, 2004) University of Regina. Dean of Science.
Open Access
Department of Mathematics and Statistics Annual Report 2004
(Department of Mathematics and Statistics, University of Regina, 2004) University of Regina. Dept. of Mathematics & Statistics.
Open Access
Creating our future: 2005-2010 : a strategic plan for the Faculty of Science
(Faculty of Science, University of Regina, 2004-09) University of Regina. Faculty of Science.
Open Access
Faculty of Science annual report, January 1, 2005 - December 31, 2005
(Faculty of Science, University of Regina, 2005) University of Regina. Dean of Science.
Open Access
Faculty of Science annual report, January 1, 2006 - December 31, 2006
(Faculty of Science, University of Regina, 2006) University of Regina. Dean of Science.
Open Access
Faculty of Science annual report, January 1, 2007 - December 31, 2007
(Faculty of Science, University of Regina, 2007) University of Regina. Dean of Science.
Open Access
A note on the fixed-point iteration for the matrix equations $X\pm A^*X^{-1}A=I$
(Elsevier, 2008) Fital, Sandra; Guo, Chun-Hua
The fixed-point iteration is a simple method for finding the maximal Hermitian positive definite solutions of the matrix equations $X\pm A^*X^{-1}A=I$ (the plus/minus equations). The convergence of this method may be very slow if the initial matrix is not chosen carefully. A strategy for choosing better initial matrices has been recently proposed by Ivanov, Hasanov and Uhlig. They proved that this strategy can improve the convergence in general and observed from numerical experiments that dramatic improvement happens for the plus equation with some matrices $A$. It turns out that the matrices $A$ are normal for those examples. In this note we prove a result that explains the dramatic improvement in convergence for normal (and thus nearly normal) matrices for the plus equation. A similar result is also proved for the minus equation.
Open Access
Detecting and solving hyperbolic quadratic eigenvalue problems
(SIAM, 2009) Guo, Chun-Hua; Higham, Nicholas J.; Tisseur, Francoise
Hyperbolic quadratic matrix polynomials $Q(\lambda) = \lambda^2 A + \lambda B + C$ are an important class of Hermitian matrix polynomials with real eigenvalues, among which the overdamped quadratics are those with nonpositive eigenvalues. Neither the definition of overdamped nor any of the standard characterizations provides an efficient way to test if a given $Q$ has this property. We show that a quadratically convergent matrix iteration based on cyclic reduction, previously studied by Guo and Lancaster, provides necessary and sufficient conditions for $Q$ to be overdamped. For weakly overdamped $Q$ the iteration is shown to be generically linearly convergent with constant at worst 1/2, which implies that the convergence of the iteration is reasonably fast in almost all cases of practical interest. We show that the matrix iteration can be implemented in such a way that when overdamping is detected a scalar $\mu < 0$ is provided that lies in the gap between the $n$ largest and $n$ smallest eigenvalues of the $n \times n$ quadratic eigenvalue problem (QEP) $Q(\lambda)x = 0$. Once such a $\mu$ is known, the QEP can be solved by linearizing to a definite pencil that can be reduced, using already available Cholesky factorizations, to a standard Hermitian eigenproblem. By incorporating an initial preprocessing stage that shifts a hyperbolic $Q$ so that it is overdamped, we obtain an efficient algorithm that identifies and solves a hyperbolic or overdamped QEP maintaining symmetry throughout and guaranteeing real computed eigenvalues.
Open Access
Convergence Analysis of the Doubling Algorithm for Several Nonlinear Matrix Equations in the Critical Case
(SIAM, 2009) Chiang, Chun-Yueh; Chu, Eric King-Wah; Guo, Chun-Hua; Huang, Tsung-Ming; Lin, Wen-Wei; Xu, Shu-Fang
In this paper, we review two types of doubling algorithm and some techniques for analyzing them. We then use the techniques to study the doubling algorithm for three different nonlinear matrix equations in the critical case. We show that the convergence of the doubling algorithm is at least linear with rate 1/2. As compared to earlier work on this topic, the results we present here are more general, and the analysis here is much simpler.
Open Access
An Improved Arc Algorithm for Detecting Definite Hermitian Pairs
(SIAM, 2009) Guo, Chun-Hua; Higham, Nicholas J.; Tisseur, Francoise
A 25-year old and somewhat neglected algorithm of Crawford and Moon attempts to determine whether a given Hermitian matrix pair $(A,B)$ is definite by exploring the range of the function $f(x) = x^*(A + iB)x/|x^*(A + iB)x|$, which is a subset of the unit circle. We revisit the algorithm and show that with suitable modifications and careful attention to implementation details it provides a reliable and efficient means of testing definiteness. A clearer derivation of the basic algorithm is given that emphasizes an arc expansion viewpoint and makes no assumptions about the definiteness of the pair. Convergence of the algorithm is proved for all $(A,B)$, definite or not. It is shown that proper handling of three details of the algorithm is crucial to the efficiency and reliability: how the midpoint of an arc is computed, whether shrinkage of an arc is permitted, and how directions of negative curvature are computed. For the latter, several variants of Cholesky factorization with complete pivoting are explored and the benefits of pivoting demonstrated. The overall cost of our improved algorithm is typically just a few Cholesky factorizations. Applications of the algorithm are described to testing the hyperbolicity of a Hermitian quadratic matrix polynomial, constructing conjugate gradient methods for sparse linear systems in saddle point form, and computing the Crawford number of the pair $(A,B)$ via a quasiconvex univariate minimization problem.
Open Access
Convergence rates of some iterative methods for nonsymmetric algebraic Riccati equations arising in transport theory
(Elsevier, 2010) Guo, Chun-Hua; Lin, Wen-Wei
We determine and compare the convergence rates of various fixed-point iterations for finding the minimal positive solution of a class of nonsymmetric algebraic Riccati equations arising in transport theory.
Open Access
The matrix equation $X+A^TX^{-1}A=Q$ and its application in nano research
(SIAM, 2010) Guo, Chun-Hua; Lin, Wen-Wei
The matrix equation $X+A^TX^{-1}A=Q$ has been studied extensively when $A$ and $Q$ are real square matrices and $Q$ is symmetric positive definite. The equation has positive definite solutions under suitable conditions, and in that case the solution of interest is the maximal positive definite solution. The same matrix equation plays an important role in Green's function calculations in nano research, but the matrix $Q$ there is usually indefinite (so the matrix equation has no positive definite solutions) and one is interested in the case where the matrix equation has no positive definite solutions even when $Q$ is positive definite. The solution of interest in this nano application is a special weakly stabilizing complex symmetric solution. In this paper we show how a doubling algorithm can be used to find good approximations to the desired solution efficiently and reliably.
Open Access
Solving a structured quadratic eigenvalue problem by a structure-preserving doubling algorithm
(SIAM, 2010) Guo, Chun-Hua; Lin, Wen-Wei
In studying the vibration of fast trains, we encounter a palindromic quadratic eigenvalue problem (QEP) $(\lambda^2 A^T + \lambda Q + A)z = 0$, where $A, Q \in \mathbb{C}^{n \times n}$ and $Q^T = Q$. Moreover, the matrix $Q$ is block tridiagonal and block Toeplitz, and the matrix $A$ has only one nonzero block in the upper-right corner. So most of the eigenvalues of the QEP are zero or infinity. In a linearization approach, one typically starts with deflating these known eigenvalues, for the sake of efficiency. However, this initial deflation process involves the inverses of two potentially ill-conditioned matrices. As a result, large error might be introduced into the data for the reduced problem. In this paper we propose using the solvent approach directly on the original QEP, without any deflation process. We apply a structure-preserving doubling algorithm to compute the stabilizing solution of the matrix equation $X+A^TX^{-1}A=Q$, whose existence is guaranteed by a result on the Wiener--Hopf factorization of rational matrix functions associated with semi-infinite block Toeplitz matrices and a generalization of Bendixson's theorem to bounded linear operators on Hilbert spaces. The doubling algorithm is shown to be well defined and quadratically convergent. The complexity of the doubling algorithm is drastically reduced by using the Sherman--Morrison--Woodbury formula and the special structures of the problem. Once the stabilizing solution is obtained, all nonzero finite eigenvalues of the QEP can be found efficiently and with the automatic reciprocal relationship, while the known eigenvalues at zero or infinity remain intact.
Open Access
On Newton's method and Halley's method for the principal $p$th root of a matrix
(Elsevier, 2010) Guo, Chun-Hua
If $A$ is a matrix with no negative real eigenvalues and all zero eigenvalues of $A$ are semisimple, the principal $p$th root of $A$ can be computed by Newton's method or Halley's method, with a preprocessing procedure if necessary. We prove a new convergence result for Newton's method, and discover an interesting property of Newton's method and Halley's method in terms of series expansions. We explain how the convergence of Newton's method and Halley's method can be improved when the eigenvalues of $A$ are known or when $A$ is a singular matrix. We also prove new results on $p$th roots of $M$-matrices and $H$-matrices, and consider the application of Newton's method and Halley's method to find the principal $p$th roots of these special matrices.
Open Access
Complex symmetric stabilizing solution of the matrix equation $X+A^{T}X^{-1}A=Q$
(Elsevier, 2011) Guo, Chun-Hua; Kuo, Yueh-Cheng; Lin, Wen-Wei
We study the matrix equation $X+A^{T}X^{-1}A=Q$, where $A$ is a complex square matrix and $Q$ is complex symmetric. Special cases of this equation appear in Green's function calculation in nano research and also in the vibration analysis of fast trains. In those applications, the existence of a unique complex symmetric stabilizing solution has been proved using advanced results on linear operators. The stabilizing solution is the solution of practical interest. In this paper we provide an elementary proof of the existence for the general matrix equation, under an assumption that is satisfied for the two special applications. Moreover, our new approach here reveals that the unique complex symmetric stabilizing solution has a positive definite imaginary part. The unique stabilizing solution can be computed efficiently by the doubling algorithm.
Open Access
Simultaneous Tracking and Activity Recognition with Relational Dynamic Bayesian Networks
(Department of Computer Science, University of Regina, 2011-03-30) Manfredotti, Cristina Elena; Fleet, David James; Hamilton, Howard John; Zilles, Sandra
Taking into account relationships between interacting objects can improve the understanding of the dynamic model governing their behaviors. Moreover, maintaining a belief about the ongoing activity while tracking allows online activity recognition and improves the tracking task. We investigate the use of Relational Dynamic Bayesian Networks to represent the relationships for the tasks of multi-target tracking and explicitly consider a discrete variable in the state to represent the activity for online activity recognition. We propose a new transition model that accommodates relations and activities and we extend the Particle Filter algorithm to directly track relations between targets while recognizing ongoing activities.