UC Irvine

Kinematic synthesis, at its heart, involves finding the zero-dimensional solution set of a

system of polynomials. The degree of these polynomials increases rapidly as more com

plex designs are considered. The computation time required to find the solution set has

traditionally been the bounding factor for what can been achieved in kinematic synthesis.

Homotopy continuation is typically used to find solutions to these polynomials. Homotopy

continuation is itself an inherently parallelizable method. Graphics processing units (GPUs)

were developed were developed with a structure that makes them optimal to solve problems

in parallel. This dissertation explores the use of homotopy continuation running a GPU in

order to decrease the computation time required for kinematic synthesis.

First, we discuss the development of an algorithm for homotopy continuation that is ideal

to run on a GPU. The traditional path tracking algorithm is analyzed and then modified to

better perform on a GPU. Additionally, the endgame methods are analyzed and the more

ideal method is identified and implemented in CUDA. We outline the drawbacks of such

modifications and discuss why they are admissible in the context of kinematic synthesis.

The implementation of the new homotopy continuation algorithm on a GPU is demon

strated by solving the four-bar linkage synthesis problem. This is the first development of

a GPU-accelerated four-bar linkage design system. Novel (non-Burmester) loop equations

are derived such that the entire mechanism is solved in one computation. These equations

are then reduced and implemented into CUDA. The entire program is outlined and then

demonstrated on a sample design problem. The results are compared with a similar CPU

implemented system and a GPU speedup of around 120 times was observed.

The results of the four-bar linkage design system were then extended to the problem of six

bar linkage synthesis. A system was developed utilizing the same GPU-based path tracker

and endgame. This has resulted in the first known GPU-accelerated six-bar linkage design

system that presents new opportunities for multi-GPU systems capable of designing even

more complicated mechanisms.