Abstract:
This project consists of developing an algorithm that performs a grid search with minimal computation and short run-time. The goal of a grid search is to approximate an unknown function that defines a set. The algorithm can test whether an individual point is inside or outside of the set. Using this information, the algorithm iterates through the grid points and determines which points are in the set. Professor Zachary Feinstein made MATLAB code that performs a grid search, although the program has a long run-time, especially when performed on grids in more than two dimensions. This drawback poses a need for an algorithm that selects points in a more intelligent way. Selecting fewer points can decrease run-time and improve efficiency. The improved algorithm utilizes MATLAB’s parallel processing capabilities. The grid search starts on a sparse grid, then identifies regions close to the set boundary. The selected regions are then treated as separate grids. The grid search is performed on new grid points located inside each new grid. This process increases the number of total grid points, which allows for a closer approximation of the set’s boundary. The structure of the improved algorithm allows the computer to take advantage of its multiple cores, in which regions are analyzed simultaneously. Run-time is shorter as a result. The process of dividing the grid into regions is repeated, recursively, until the desired accuracy is obtained. The algorithm then returns the boundary of the set, which approximates the unknown function.
This project consists of developing an algorithm that performs a grid search with minimal computation and short run-time. The goal of a grid search is to approximate an unknown function that defines a set. The algorithm can test whether an individual point is inside or outside of the set. Using this information, the algorithm iterates through the grid points and determines which points are in the set. Professor Zachary Feinstein made MATLAB code that performs a grid search, although the program has a long run-time, especially when performed on grids in more than two dimensions. This drawback poses a need for an algorithm that selects points in a more intelligent way. Selecting fewer points can decrease run-time and improve efficiency. The improved algorithm utilizes MATLAB’s parallel processing capabilities. The grid search starts on a sparse grid, then identifies regions close to the set boundary. The selected regions are then treated as separate grids. The grid search is performed on new grid points located inside each new grid. This process increases the number of total grid points, which allows for a closer approximation of the set’s boundary. The structure of the improved algorithm allows the computer to take advantage of its multiple cores, in which regions are analyzed simultaneously. Run-time is shorter as a result. The process of dividing the grid into regions is repeated, recursively, until the desired accuracy is obtained. The algorithm then returns the boundary of the set, which approximates the unknown function.