**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Fast continuous Fourier and Haar transforms of rectilinear polygons from very-large-scale integration layouts

Abstract

We propose two new fast algorithms for the computation of the continuous Fourier series and the continuous Haar transform of rectilinear polygons such as those of mask layouts in optical lithography. These algorithms outperform their discrete counterparts traditionally used. Not only are continuous transforms closer to the underlying continuous physical reality, but they also avoid the inherent inaccuracies introduced by the sampling or rasterization of the polygons in the discrete case. Moreover, massive amounts of data and the intense processing methods used in lithography require efficient algorithms at every step of the process. We derive the complexity of each algorithm and compare it to that of the corresponding discrete transform. For the practical very-large-scale integration (VLSI) layouts, we find significant reduction in the complexity because the number of polygon vertices is substantially smaller than the corresponding discrete image. This analysis is completed by an implementation and a benchmark of the continuous algorithms and their discrete counterparts. We run extensive experiments and show that on tested VLSI layouts the pruned continuous Haar transform is 5 to 25 times faster, while the fast continuous Fourier series is 1.5 to 3 times faster than their discrete counterparts.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (2)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Fourier transform

In physics and mathematics, the Fourier transform (FT) is a transform that converts a function into a form that describes the frequencies present in the original function. The output of the transform is a complex-valued function of frequency. The term Fourier transform refers to both this complex-valued function and the mathematical operation. When a distinction needs to be made the Fourier transform is sometimes called the frequency domain representation of the original function.