Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Annotation of /trunk/doc/field-norm/paper.tex
ViewVC logotype

Annotation of /trunk/doc/field-norm/paper.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 468 - (view) (download) (as text)

1 : jhr 468 \documentclass[11pt]{article}
2 :    
3 :     \setlength{\textwidth}{6in}
4 :     \setlength{\oddsidemargin}{0.25in}
5 :     \setlength{\evensidemargin}{0.25in}
6 :     \setlength{\parskip}{5pt}
7 :    
8 :     \input{defs}
9 :    
10 :     \title{Normalization of Field and Probe Expressions}
11 :     \author{
12 :     John Reppy \\
13 :     University of Chicago \\
14 :     {\small\tt{}jhr@cs.uchicago.edu} \\
15 :     }
16 :     \date{\today}
17 :    
18 :     \newcommand{\Fnorm}[1]{\mathcal{F}\LDB{}#1\RDB{}}
19 :     \newcommand{\Pnorm}[1]{\mathcal{P}\LDB{}#1\RDB{}}
20 :    
21 :     \begin{document}
22 :    
23 :     \maketitle
24 :     \thispagestyle{empty}
25 :    
26 :     \bibliographystyle{../common/alpha}
27 :     \bibliography{../common/strings-short,../common/manticore}
28 :    
29 :     \section{Introduction}
30 :    
31 :     This note describes the symbolic transformations that are applied to field and probe expressions in
32 :     the Diderot compiler.
33 :     The purpose of these transformations is to make the actual compilation of probe operations
34 :     more straightforward.
35 :     We describe these transformations using three simple expression languages.
36 :     The first corresponds to the Diderot surface-language syntax for field and probe expressions.
37 :     The second language has the property that derivative operations have been pushed down to the
38 :     convolution kernels, and the third language reduces probes to work on images.
39 :    
40 :     \section{The formal model}
41 :    
42 :     In the discussion below, we use a number of notational conventions that are
43 :     summarized in the following table:
44 :     \begin{center}
45 :     \begin{tabular}{cp{4in}}
46 :     $V$ & an image \\
47 :     $F$, $G$ & fields \\
48 :     $h$ & a piecewise polynomial convolution kernel \\
49 :     $s$ & a scalar \\
50 :     $\vecx$ & a position in world space
51 :     \end{tabular}%
52 :     \end{center}%
53 :    
54 :     The source language of field expressions is
55 :     \begin{displaymath}
56 :     \begin{array}{rcll}
57 :     F & ::= & V\circledast{}h & \text{convolution} \\
58 :     & \mid & F+G & \text{addition} \\
59 :     & \mid & s F & \text{scaling} \\
60 :     & \mid & \nabla{}F & \text{differentiation}
61 :     \end{array}%
62 :     \end{displaymath}%
63 :     We normalize these expressions by pushing the differentiation operators down to the
64 :     kernels, which results in the following language of field expressions:
65 :     \begin{displaymath}
66 :     \begin{array}{rcll}
67 :     \hat{F} & ::= & V\circledast{}h^k & \text{convolution with $k$th derivative of $h$} \\
68 :     & \mid & \hat{F}+\hat{G } & \text{addition} \\
69 :     & \mid & s \hat{F} & \text{scaling} \\
70 :     \end{array}%
71 :     \end{displaymath}%
72 :     The normalization rules are as follows:
73 :     \begin{eqnarray*}
74 :     \Fnorm{\nabla{}(V\circledast{}h^k)} & = & V\circledast{}h^{k+1} \\
75 :     \Fnorm{\nabla{}(F+G)} & = & \Fnorm{\nabla{}F} + \Fnorm{\nabla{}G} \\
76 :     \Fnorm{\nabla{}(s F)} & = & s \Fnorm{\nabla{}F}
77 :     \end{eqnarray*}%
78 :    
79 :     The syntax of probe operations (after field normalization) is
80 :     \begin{displaymath}
81 :     \hat{F}\mkw{@}\vecx
82 :     \end{displaymath}%
83 :     We normalize these expressions by pushing the probes down to the leaves
84 :     and rewriting them as probes into images with the following syntax
85 :     \begin{displaymath}
86 :     V\mkw{@}_{h^k}\vecx
87 :     \end{displaymath}%
88 :     The normalization rules are as follows:
89 :     \begin{eqnarray*}
90 :     \Pnorm{(V\circledast{}h^k)\mkw{@}\vecx} & = & V\mkw{@}_{h^k}\vecx \\
91 :     \Pnorm{(F+G)\mkw{@}\vecx} & = & \Pnorm{F\mkw{@}\vecx} + \Pnorm{G\mkw{@}\vecx} \\
92 :     \Pnorm{(s F)\mkw{@}\vecx} & = & s \Pnorm{F\mkw{@}\vecx}
93 :     \end{eqnarray*}%
94 :    
95 :     \section{Implementation in the compiler}
96 :     These transformations are mostly implemented on the SimpleAST representation.
97 :    
98 :     \end{document}

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0