Faculty of Engineering
https://dspace.library.uvic.ca//handle/1828/74
2017-11-22T03:36:48ZSystematic parameterized complexity analysis in computational phonology
https://dspace.library.uvic.ca//handle/1828/8806
Systematic parameterized complexity analysis in computational phonology
Wareham, Harold
Many computational problems are NP-hard and hence probably do not have fast, i.e., polynomial time, algorithms. Such problems may yet have non-polynomial time algorithms, and the non-polynomial time complexities of these algorithm will be functions of particular aspects of that problem, i.e., the algorithm's running time is upper bounded by f (k) |x|ᶜ, where f is an arbitrary function, |x| is the size of the input x to the algorithm, k is an aspect of the problem, and c is a constant independent of |x| and k. Given such algorithms, it may still be possible to obtain optimal solutions for large instances of NP-hard problems for which the appropriate aspects are of small size or value. Questions about the existence of such algorithms are most naturally addressed within the theory of parameterized computational complexity developed by Downey and Fellows.
This thesis considers the merits of a systematic parameterized complexity analysis in which results are derived relative to all subsets of a specified set of aspects of a given NP-hard problem. This set of results defines an “intractability map” that shows relative to which sets of aspects algorithms whose non-polynomial time complexities are purely functions of those aspects do and do not exist for that problem. Such maps are useful not only for delimiting the set of possible algorithms for an NP-hard problem but also for highlighting those aspects that are responsible for this NP-hardness.
These points will be illustrated by systematic parameterized complexity analyses of problems associated with five theories of phonological processing in natural languages—namely, Simplified Segmental Grammars, finite-state transducer based rule systems, the KIMMO system, Declarative Phonology, and Optimality Theory. The aspects studied in these analyses broadly characterize the representations and mechanisms used by these theories. These analyses suggest that the computational complexity of phonological processing depends not on such details as whether a theory uses rules or constraints or has one, two, or many levels of representation but rather on the structure of the representation-relations encoded in individual mechanisms and the internal structure of the representations.
2017-11-20T00:00:00ZA quantitative concurrent engineering design method using virtual prototyping-based global optimization and its application in transportation fuel cells
https://dspace.library.uvic.ca//handle/1828/8804
A quantitative concurrent engineering design method using virtual prototyping-based global optimization and its application in transportation fuel cells
Wang, Gaofeng Gary
Concurrent engineering and virtual prototyping are two emerging techniques that are bringing considerable economical benefits to the manufacturing industry. This work proposes the use of virtual prototyping to produce quantitative measures of product lifecycle performances to facilitate the implementation of concurrent engineering. A multiobjective, virtual prototyping-based global optimization problem is formulated to close the open loop of present virtual prototyping methods and to allow concurrent engineering design to be carried out systematically and automatically.
Virtual prototyping-based design optimization faces several technical challenges. First, virtual prototyping is usually computationally intensive; relations between design variables and product life-cycle performances are often implicit. Secondly, the optimization problem usually consists of multi-modal design (objective and constraint) functions. The complexity and multi-modal nature of the optimization problem preclude the direct use of conventional local and global optimization methods. In this work, a new and efficient search method for virtual prototyping-based global design optimization is introduced. The method, called Adaptive Response Surface Method (ARSM), carries out systematic “design experiments” through virtual prototyping to build second-order regression models to approximate the design functions. Through an iterative process, the regression models are improved and the global design optimum is obtained. The ARSM search scheme requires only a modest number of design function evaluations, making virtual prototyping-based global design optimization feasible.
The proposed quantitative concurrent design method is then applied to the components, stack and system design of a transportation fuel cell. The approach led to an optimized multi-functional component, a reduction of the system cost, and an improvement of the system performance. The approach can be applied to the concurrent design and design optimization of other complex mechanical components, assemblies and systems.
2017-11-17T00:00:00ZNumerical and experimental modelling of an oscillating wave surge converter in partially standing wave systems
https://dspace.library.uvic.ca//handle/1828/8802
Numerical and experimental modelling of an oscillating wave surge converter in partially standing wave systems
Bocking, Bryce
In the field of ocean wave energy converters (WECs), active areas of research are on a priori or in situ methods for power production estimates and on control system design. Linear potential flow theory modelling techniques often underpin these studies; however, such models rely upon small wave and body motion amplitude assumptions and therefore cannot be applied to all wave conditions. Nonlinear extensions can be applied to the fluid loads upon the structure to extend the range of wave conditions for which these models can provide accurate predictions. However, careful consideration of the thresholds of wave height and periods to which these models can be applied is still required. Experimental modelling in wave tank facilities can be used for this purpose by comparing experimental observations to numerical predictions using the experimental wave field as an input.
This study establishes a recommended time domain numerical modeling approach for power production assessments of oscillating wave surge converters (OWSCs), a class of WEC designed to operate in shallow and intermediate water depths. Three candidate models were developed based on nonlinear numerical modelling techniques in literature, each with varying levels of complexity. Numerical predictions provided by each model were found to be very similar for small wave amplitudes, but divergence between the models was observed as wave height increased.
Experimental data collected with a scale model OWSC for a variety of wave conditions was used to evaluate the accuracy of the candidate models. These experiments were conducted in a small-scale wave flume at the University of Victoria. A challenge with this experimental work was managing wave reflections from the boundaries of the tank, which were significant and impacted the dynamics of the scale model OWSC. To resolve this challenge, a modified reflection algorithm based upon the Mansard and Funke method was created to identify the incident and reflected wave amplitudes while the OWSC model is in the tank. Both incident and reflected wave amplitudes are then input to the candidate models to compare numerical predictions with experimental observations.
The candidate models agreed reasonably well with the experimental data, and demonstrated the utility of the modified wave reflection algorithm for future experiments. However, the maximum wave height generated in the wave tank was found to be limited by the stroke length of the wavemaker. As a result, no significant divergence of the candidate model predictions from the experimental data could be observed for the limited range of wave conditions, and therefore a recommended model could not be selected based solely on the experimental/numerical model comparisons.
Preliminary assessments of the annual power production (APP) for the OWSC were obtained for a potential deployment site on the west coast of Vancouver Island. Optimal power take-off (PTO) settings for the candidate models were identified using a least-squares optimization to maximize power production for a given set of wave conditions. The power production of the OWSC at full scale was then simulated for each bin of a wave histogram representing one year of sea states at the deployment site. Of the three candidate models, APP estimates were only obtained for Model 1, which has the lowest computational requirements, and Model 3, which implements the most accurate algorithm for computing the fluid loads upon the OWSC device. Model 2 was not considered as it provides neither advantages of Models 1 and 3.
The APP estimates from Models 1 and 3 were 337 and 361 MWh per year. For future power production assessments, Model 3 is recommended due to its more accurate model of the fluid loads upon the OWSC. However, if the high computational requirements of Model 3 are problematic, then Model 1 can be used to obtain a slightly conservative estimate of APP with a much lower computational effort.
2017-11-17T00:00:00ZSwitching and error recovery in terabit ATM networks
https://dspace.library.uvic.ca//handle/1828/8798
Switching and error recovery in terabit ATM networks
Sabaa, Amr Gaber
This thesis addresses two of the main issues required to build reliable terabit ATM networks.
A high-capacity switch and an efficient error recovery protocol are the key elements
in building a reliable terabit ATM network. In this thesis, a terabit switch architecture and
a reliable end-to-end error recovery protocol for terabit networks are introduced.
The proposed terabit ATM switch architecture is designed to work efficiently in low-capacity
and high-capacity environments. The architecture is developed by interconnecting
small-capacity switching modules in a scalable fashion. The switching module can be used
alone as a small-capacity ATM switch. Multiple the switching modules can be used to
achieve any required switching capacity. The proposed interconnecting scheme provides remarkable
low cell-delay characteristics with a simple distributed cell scheduler. The proposed
architecture has a high reliability: Even when a complete switching module fails the
switch will continue to work efficiently.
The switching element which is introduced as the main building block for the terabit
switch architecture is a nonblocking input buffer ATM switch. The input buffers are implemented
as groups of parallel shift-registers. The parallel nature of the storing buffers overcomes
the Head Of Line and low throughput problems of existing input buffer switch architectures.
In addition, using the shift registers overcomes the need for serial-to-parallel
and parallel-to-serial format conversions.
ATM networks support different types of services having different delay and loss requirements.
A priority scheduling scheme is proposed to facilitate the support of different
Qualities of Service. The proposed scheme satisfies both real-time and non-real-time service
requirements.
Cell loss is not acceptable for some data applications. This thesis proposes an efficient error recovery protocol which guarantees reliable communication with limited overhead.
The proposed protocol requires a low number of control packets to achieve reliable communication.
It also adapts itself, in order to work efficiently during both congested and non congested
states.
2017-11-15T00:00:00Z