text:
# Reverse an integer, find the absolute difference, then reverse again

For one of my university assignments, we were asked to take an unsigned int, reverse its digits, find the absolute difference between the original and reversed, then reverse that, and you receive the "Magic Number".

$$R(\ \lvert R(A) - A\rvert\ )$$

where $A$ is a positive integer and $R(n)$ means reverse.

We were also asked to take multiple inputs at once and keep track of the largest absolute difference between all inputs.

#include <stdio.h>

// Reverse an unsigned integer
unsigned int reverseInteger(unsigned int input) {

unsigned int output = 0;

while (input != 0) { // Terminate when input is 0
output = output * 10 + input % 10; // Can't use =* here, order of operations!
input /= 10;
}

return output;
}

// Find the absolute differnece between a reversed number, then reverse the absolute difference
unsigned int generateMagicNumber(unsigned int input) {

/* Find Absolute Difference */
if (input < reverseInteger(input)) {
input = reverseInteger(input); // If the result will be negative, reverse the number before finding the difference
input -= reverseInteger(input);
}
else {
input -= reverseInteger(input);
}

largestAbsoluteDifference(input);

return reverseInteger(input); // Reverse absolute difference to find the magic number

}

// Find the largest of all values passed to this function
unsigned int largestAbsoluteDifference(unsigned int input) {

static unsigned int keep = 0; // Must be static!

return (input > keep) ? (keep = input) : keep; // If the input is greater than the current, store the input. Else, keep the current.

}

int main() {

int inputs;
printf("Enter number of inputs: ");
scanf("%d", &inputs);
printf("Enter space separated: ");

for (int i = 0; i < inputs; i++) {
unsigned int num;
scanf("%u", &num);

if (i == 0) { printf("\nOutput: "); } // Append label only on first iteration

printf("%u ", generateMagicNumber(num)); // Generate and print the magic number
}

printf("\nLargest Absolute Difference: %u\n", largestAbsoluteDifference(0)); // Must pass 0 into largestAbsoluteDifference

}

Example Input / Output

Enter number of inputs: 5
Enter space separated: 23 512 454 94 100

Output: 9 792 0 54 99
Largest Absolute Difference: 297

Notes / Concerns

• The way I wrote the largestAbsoluteDifference seems slimy me to (having to pass 0 to get the result).
• I've got in the habit of calling functions inside a printf instead of storing the value in a variable and then printing the variable (see lines 56, 59). Is this okay?
• In generateMagicNumber I had to make sure finding the difference wouldn't result in a negative number (which you can't store in an unsigned int). Is my method the best way to find the absolute value like that?
• Is R intended to be bijective? As implemented reverseInteger(90) yields 9, which when reversed again yields 9. If bijectivity is required, then you might have to operate on strings... – Matthieu M. Jan 28 '16 at 17:32
• @MatthieuM. No. As it works is how it should. Good thing to point out, though! – Insane Jan 29 '16 at 3:43

You write unsigned int enough times that it's probably worthwhile to typedef it, in caseunsigned int turns out to be too small. (Keep in mind that it is only guaranteed to go up to 65535.)

typedef unsigned int number;
#define NUMBER_FMT "%u"

The reverseInteger() function is fine. I'd rename it for clarity, then remove the superfluous comments.

/**
* Reverse the digits of a number
*/
number reverseDigits(number input) {
number output = 0;

while (input != 0) {
output = output * 10 + input % 10;
input /= 10;
}

return output;
}

The code in generateMagicNumber() was really hard to follow. The call reverseInteger(input) appears five times in that function. One codepath has four of those calls, and the other has three. Not only is that suboptimal1, it's also confusing because the input refers to a different number each time even though they all look the same. Please avoid repurposing variables like that.

/**
* The reverse of the absolute difference between a number and its reverse
*/
number magic(number input) {
number rev = reverseDigits(input);
number absDiffWithReverse = (rev > input) ? rev - input : input - rev;
return reverseDigits(absDiffWithReverse);
}

The ugly part of the problem is the requirement to keep track of the largest $\lvert R(A) - A \rvert$. I see four unpalatable options:

1. As you have done, insert code inside generateMagicNumber() to capture the intermediate computational result.

The disadvantages are that you are doing this as a side-effect, and using static (or global) state. That kind of statefulness would become a maintenance headache on larger projects. You also had to use a funny hack of calling largestAbsoluteDifference(0) to read out the maximum.

2. Instead of defining generateMagicNumber(), define absDiffWithReverse() to calculate $\lvert R(A) - A \rvert$. Then, let main() be responsible for tracking the maximum of those.

To get the magic numbers, main() would need to finish the job by reversing them. It's a bit dissatisfying that, for a program whose primary purpose is to compute "magic numbers", there is no magic-number-computing function.

3. Define a function to compute both the magic number and the $\lvert R(A) - A \rvert$ intermediate result.

Since C only allows one return value, you could either return a struct with two numbers or pass back one of the values as an out-parameter. I find both techniques aesthetically unpleasing, especially since those two results can be trivially derived from each other.

4. Define a function to compute the magic number. To get the $\lvert R(A) - A \rvert$, reverse the magic number again.

As @MatthieuM has pointed out, reversing the digits twice could change the result, due to the possibility of trailing or leading zeroes.

I think I would prefer option 3:

number magic(number input, number *absDiffWithReverse) {
number rev = reverseDigits(input);
*absDiffWithReverse = (rev > input) ? rev - input : input - rev;
return reverseDigits(*absDiffWithReverse);
}

number max(number a, number b) {
return a > b ? a : b;
}

int main() {
int inputs;
printf("Enter number of inputs: ");
scanf("%d", &inputs);
printf("Enter space separated: ");

number maxDiffRev = 0;
for (int i = 0; i < inputs; i++) {
number n, nMagic, absDiffRev;
scanf(NUMBER_FMT, &n);
// Print label only on first iteration
if (i == 0) { printf("\nOutput: "); }

nMagic = magic(n, *absDiffRev);
printf(NUMBER_FMT " ", nMagic);
maxDiffRev = max(maxDiffRev, *absDiffRev);
}

printf("\nLargest Absolute Difference: " NUMBER_FMT "\n", maxDiffRev);
}

1. Yes, calling largestAbsoluteDifference(0) to read the maximum is slimy. Ideally, static state should be avoided altogether.
2. Calling functions inside printf() calls is fine if they are pure functions with no side-effects. It's not as good a practice if the function being called has side-effects. I wouldn't worry about it in your case. What I wrote above, with a variable assignment inside a printf() call, is probably far more controversial.
3. Your technique is arithmetically correct, but not recommended due to the input variable shifting its meaning.

1 Not that performance really matters here. What I'm pointing out is silliness more than a serious efficiency problem.

Using static local variables like that is not a good idea for a few reasons. First there is no way to reset it for the next run. It's also not thread safe.

Instead pull that out into the main function:

unsigned int largest = 0;

for (int i = 0; i < inputs; i++) {
unsigned int num;
scanf("%u", &num);

if (i == 0) { printf("\nOutput: "); } // Append label only on first iteration
unsigned int magicNumber = generateMagicNumber(num)
printf("%u ", magicNumber ); // Generate and print the magic number

if(magicNumber > largest) largest = magicNumber;
}

printf("\nLargest Absolute Difference: %u\n", largest);

For generating the magic number you can call reverseInteger just once and then store the input:

unsigned int generateMagicNumber(unsigned int input) {

unsigned int reverse = reverseInteger(input);
/* Find Absolute Difference */
if (input < reverse) {
input = reverse - input;
}
else {
input -= reverse;
}

return reverseInteger(input); // Reverse absolute difference to find the magic number

}

• I think you oversimplified it: largest must consider the absolute difference (and not the magic number) - see the answer of @200_success – oliverpool Jan 28 '16 at 12:15
• Think the correct term is reentrant, not threadsafe, if you add locks to a code that read*/writes to statics or global's it is thread safe, but not reeantrant. *read from constants is always safe of course. – fhtuft Jan 28 '16 at 13:31
• @fhtuft non-reentrant in a non-recursive context generally means not thread safe – ratchet freak Jan 28 '16 at 13:39


text:
# Assistance in checking transfer function

Hi,

I am undertaking an undergrad design project and want to ensure I'm doing this correctly,

I have derived the ODE as shown below;

A*Y = M*X'' + (B+C)*X' + D*X
Where A,M,B,C,D are constants.

By taking the Laplace transform, I get;
A*Y(s) = M*s^2*X(s) + (B+C)*s*X(s) + D*X(s)

Therefore,
My transfer function becomes;

TF(s) = X(s)/Y(s) = the image of the transfer function below;
http://imageshack.us/a/img37/8820/95533304.jpg [Broken]

Feedback on this would be much appreciated.

Last edited by a moderator:

$Q(s)X_{out}(s) = P(s)X_{in}(s) \; \Rightarrow \; H(s) = \frac{P(s)}{Q(s)} = \frac{X_{out}(s)}{X_{in}(s)}$

format: plain


text:
Rectangular diagrams of surfaces: representability

# Rectangular diagrams of surfaces: representability

Ivan Dynnikov and Maxim Prasolov Steklov Mathematical Institute of Russian Academy of Sciences, 8 Gubkina Str., Moscow 119991, Russia
###### Abstract.

We introduce a simple combinatorial way, which we call a rectangular diagram of a surface, to represent a surface in the three-sphere. It has a particularly nice relation to the standard contact structure on and to rectangular diagrams of links. By using rectangular diagrams of surfaces we are going, in particular, to develop a method to distinguish Legendrian knots. This requires a lot of technical work of which the present paper addresses only the first basic question: which isotopy classes of surfaces can be represented by a rectangular diagram. Vaguely speaking the answer is this: there is no restriction on the isotopy class of the surface, but there is a restriction on the rectangular diagram of the boundary link that can arise from the presentation of the surface. The result extends to Giroux’s convex surfaces for which this restriction on the boundary has a natural meaning. In a subsequent paper we are going to consider transformations of rectangular diagrams of surfaces and to study their properties. By using the formalism of rectangular diagrams of surfaces we also produce here an annulus in that we expect to be a counterexample to the following conjecture: if two Legendrian knots cobound an annulus and have zero Thurston–Bennequin numbers relative to this annulus, then they are Legendrian isotopic.

The work is supported by the Russian Science Foundation under grant 14-50-00005 and performed in Steklov Mathematical Institute of Russian Academy of Sciences.

## 1. Introduction

Rectangular diagrams of links, also known as arc-presentations and grid diagrams, have proved to be useful tool in knot theory. It is shown in [5] that any rectangular diagram of the unknot admits a monotonic simplification to a square by elementary moves. This was used by M. Lackenby to prove a polynomial bound on the number of Reidemeister moves needed to untangle a planar diagram of the unknot [22].

It is tempting to extend the monotonic simplification approach to general knots and links, but certainly it cannot be done straightforwardly. Typically a non-trivial link type admits more than one rectangular diagram that cannot be simplified further by elementary moves without using stabilizations. As shown in [6] classifying such diagrams is closely related to classifying Legendrian links not admitting a destabilization.

In particular, the main result of [6] implies that the finiteness of non-destabilizable Legendrian types in each topological link type (which is the matter of Question 61 in [4]) is equivalent to the finiteness of the number of rectangular diagrams that represent each given link type and cannot be monotonically simplified. Neither of these has been established so far.

Surfaces embedded in , either closed or bounded by a link, have always been one of the key instruments of the knot theory. For studying contact structures and Legendrian links it is useful to consider surfaces that are in special position with respect to the contact structure, so called convex surfaces. They were introduced by E. Giroux in [13] and studied also in [3, 10, 18, 21, 24].

Sometimes one can prove the existence of a convex surface having certain combinatorial and algebraic properties for one contact structure and non-existence of such a surface for the other, thus showing there is no contactomorphism between the structures. This method can be viewed as a generalization of the classical work of Bennequin [1] where he distinguishes a contact structure in from the standard one by showing that an overtwisted disc exists for the former and does not exist for the latter. Indeed, an overtwisted disc can be viewed as a disc with Legendrian boundary and a closed dividing curve.

This method can also be used to distinguish Legendrian links by applying the argument to the link complement. For instance, some Legendrian types of iterated torus knots are distinguished in [11] by showing that certain slopes on an incompressible torus in the knot complement are realized by dividing curves for one knot and not realized for the other.

Note that whereas the problem of algorithmic comparing topological types of two links has been solved (see [26]) no algorithm is known to compare Legendrian types of two Legendrian links having the same topological type. Examples of pairs of Legendrian knots for which the equivalence remains an open question start from six (!) crossings [2].

In this paper we propose a simple combinatorial way to represent compact surfaces in so that the boundary is represented in the rectangular way. The basic idea of this presentation is not quite new and is implicitly present in the literature. In particular, it can be considered as an instance of Kneser–Haken’s normal surfaces for triangulations of obtained by the join construction from triangulations of two circles .

We observe in this paper that the discussed combinatorial approach appears to be well adapted to Giroux’s convex surfaces with Legendrian boundary. In particular, we show that any convex surface with Legendrian boundary is equivalent (in a certain natural sense) to a one that can be presented in the proposed way.

By using this approach we are going to distinguish some pairs of Legendrian knots that are not distinguishable by known methods. Since a rectangular diagram of a surface is a simple combinatorial object, sometimes the non-existence of a diagram with required properties can be established by combinatorial methods. Combined with the representability result of the present paper this may be used to show the non-existence of a convex surface with certain properties in the complement of a Legendrian knot. If a convex surfaces with the same properties is known to exist for another Legendrian knot the two Legendrian types must be different. This method is out of the scope of the present paper and will be presented in a subsequent paper.

We also consider here in more detail embedded convex (in Giroux’s sense) annuli in tangent to the contact structure along the boundary. Such annuli are the main building blocks of closed convex surfaces in . We discuss the following specific question: are the two boundary components of such an annulus always equivalent as Legendrian knots?

This question appears to be highly non-trivial. An attempt to answer it in the positive was made in manuscript [17] but a complete proof was not given. We believe that the answer is actually negative, but our attempt to find a simple counterexample has failed. In a number of examples that we tried the two boundary components of the annulus appeared to be Legendrian equivalent, and a Legendrian isotopy was easily found. Namely, the boundary components were transformed to each other by elementary moves preserving the complexity of the diagram (exchange moves).

We propose here an example of an annulus of the above mentioned type whose boundary components cannot be transformed to each other without using stabilizations. We conjecture that the two Legendrian knot types in our example are different.

###### Remark 1.

Another use of rectangular diagrams of links comes from their relation to Floer homologies. As C. Manolescu, P. Ozsváth, and S. Sarkar show in [23] the definition of the knot Floer homology for links presented in the grid form can be given in purely combinatorial terms. Up to this writing, we are not aware of any useful interaction between rectangular diagrams of surfaces and algebraic theories. It would be interesting to see some.

The paper is organized as follows. In Section 2 we introduce the main subject of the paper, rectangular diagrams of surfaces, and other basic related objects. We show that every isotopy class of a surface can be presented by a rectangular diagram, but rectangular presentations of the boundary that will arise in this way satisfy certain restrictions. In Section 3 we discuss Legendrian links and graphs and their presentations by rectangular diagrams. They are used in the formulation and the proof of our main result—on the representability of convex surfaces by rectangular diagrams—which occupy Section 4. At the end of Section 4 we discuss the above mentioned conjecture about annuli with Legendrian boundary.

### Acknowledgement

We are indebted to our anonymous referee for very careful reading of our paper, which has led to many clarifications in the text.

## 2. Rectangular diagrams of a surface

### 2.1. Definitions

For any two distinct points , , say, of the oriented circle we denote by the closed arc of with endpoints , such that if it is endowed with the orientation inherited from , see Fig. 1.

By we denote the corresponding open arc: .

###### Definition 1.

A rectangle in the -torus is a subset of the form , where , , .

Two rectangles , are said to be compatible if their intersection satisfies one of the following:

1. is empty;

2. is a subset of vertices of ;

3. is a rectangle disjoint from the vertices of both rectangles and .

A rectangular diagram of a surface is a collection of pairwise compatible rectangles in  such that every meridian and every longitude of the torus contains at most two free vertices, where by a free vertex we mean a point that is a vertex of exactly one rectangle from .

To represent such a diagram graphically, we draw as a square with identified opposite sides, so, some rectangles are cut into two or four pieces,

see Fig. 2.

One can see that for any pair of compatible rectangles one of the following three mutually exclusive cases occurs:

1. the rectangles are disjoint;

2. the rectangles share , , or vertices and are otherwise disjoint;

3. the rectangles have the form (possibly after exchanging them) , with

 [θ1,θ2]⊂(θ3,θ4),[φ3,φ4]⊂(φ1,φ2).

In the latter case we draw as if it passes over , see Fig. 3.

An example of a rectangular diagram of a surface is shown in Fig. 4 on the left. The free vertices are marked by small circles.

###### Definition 2.

By a rectangular diagram of a link we mean a finite set of points in such that every meridian and every longitude of contains no or exactly two points from . The points in are referred to as vertices of .

When is presented graphically in a square, the vertical and horizontal straight line segments connecting two vertices of will be called the edges of . Formally, an edge of is a pair of vertices lying on the same longitude or meridian of . Such vertices are said to be connected by an edge, and this will have literal meaning in the pictures.

A rectangular diagram of a link is said to be connected or to be a rectangular diagram of a knot if the vertices of can be ordered so that any two consecutive vertices are connected by an edge.

A connected component of a rectangular diagram of a link is a non-empty subset that is a rectangular diagram of a knot.

###### Definition 3.

Let be a rectangular diagram of a surface. The set of free vertices of will be called the boundary of and denoted by .

It is readily seen that the boundary of a rectangular diagram of a surface is always a rectangular diagram of a link. In particular, for any rectangle the boundary of the diagram is the set of vertices of . It should not be confused with the boundary of the rectangle itself, which is understood in the conventional sense.

Fig. 4 shows a rectangular diagram of a surface (left) and its boundary (right) with edges added. The reason for drawing some edges passing over the others will be explained below.

### 2.2. Cusps and pizza slices

Here we introduce the class of topological objects (curves and surfaces) we will mostly deal with.

###### Definition 4.

Let be a piecewise smooth simple arc or simple closed curve in and a point distinct from the endpoints. We say that has a cusp at the point if admits a local parametrization such that

 limt→−0˙γ=−limt→+0˙γ≠0,γ(0)=p.

The curve is called cusp-free if it has no cusps, and cusped if all singularities of are cusps.

The links in that we consider will always be cusp-free.

###### Definition 5.

We say that is a surface with corners if is a subset of a -dimensional submanifold with (possibly empty) boundary such that:

1. the embedding is regular and of smoothness class ;

2. is bounded in by a (possibly empty) collection of mutually disjoint piecewise smooth cusp-free simple closed curves.

This definition simply means that surfaces we want to consider may have corners at the boundary, but in a broader sense than one usually means by saying ‘a manifold with corners’. Namely, the angle at a corner can be arbitrary between and (exclusive), not necessarily between and see Fig. 5.

However, surfaces with corners are not allowed to spiral around a point at the boundary as shown in Fig. 6.

For future use we also need the following definition.

###### Definition 6.

By a pizza slice centered at we mean a disc that has the form , where  is a surface with corners such that , and is a closed ball centered at with small enough radius such that has no singularities in and consists of a single arc. (The point may or may not be a singularity of .)

For such a pizza slice we also say that it is attached to the arc .

Two pizza slices , centered at the same point are said to be equivalent if for small enough the pizza slices , , are attached to the same arc and for we have , where denotes the distance function.

### 2.3. 3D realizations of rectangular diagrams

With every rectangular diagram of a link or a surface we associate an actual link or a surface, respectively, in as we now describe.

We represent as the join of two circles:

 (1) S3=S1∗S1=(S1×S1×[0,1])/((θ,φ,0)∼(θ′,φ,0), (θ,φ,1)∼(θ,φ′,1)).

We also identify it with the unit sphere in as follows:

 (θ,φ,τ)↦(cos(πτ/2)cosφ,cos(πτ/2)sinφ,sin(πτ/2)cosθ,sin(πτ/2)sinθ).

The triple will be used as a coordinate system in . The two circles defined by and will be denoted by and , respectively.

###### Definition 7.

By the torus projection of a subset we mean the image of under the map defined by .

For a point in we denote by the image of the arc in .

###### Definition 8.

Let be a rectangular diagram of a link. By the link associated with we mean the following union of arcs: .

One can see that this union is indeed a collection of pairwise disjoint simple closed piecewise smooth curves. Moreover, is a union of piecewise geodesic closed curves, which are cusp-free. One can also see that if is a connected component of , then is a connected component of  and vice versa.

To get a conventional, planar picture of a link isotopic to one cuts into a square and then join the vertices of by edges, letting the vertical edges pass over the horizontal ones, see the right picture in Fig. 4. Finally, we remark that is the torus projection of , and is the only link satisfying this property.

Cooking a surface out of a rectangular diagram of a surface is less visual, but the main principle is similar: the surface associated with a rectangular diagram of a surface should have the torus projection prescribed by the diagram. The surface associated with a rectangular diagram will be composed of discs associated with individual rectangles.

For a rectangle , the image of in under identifications (1) is the tetrahedron , which we denote by . We want to define as a disc in with boundary so that the union of such discs over all rectangles of a rectangular diagram of a surface yield a smoothly embedded surface. This can be done in numerous ways among which we choose one particularly convenient as it allows us to write down an explicit parametrization of  and behaves nicely in the respects addressed in Section 4.

We denote by a bounded harmonic function on the interior  of  that tends to as tends to or  while stays fixed, and tends to  as tends to or while stays fixed. Such a function exists and is unique, which follows from the Poisson integral formula and the uniformization theorem.

###### Remark 2.

The function admits an explicit presentation in terms of the Weierstrass elliptic function with half-periods and :

 hr(θ,φ)=1πarg℘(zθ,φ)−℘(zθ2,φ2)(℘(zθ,φ)−℘(zθ1,φ2))(℘(zθ,φ)−℘(zθ2,φ1)),

where , and are assumed to be reals satisfying , .

###### Definition 9.

We call the image in under identifications (1) of the closure of the following open disc in :

 (2) {(v,˜hr(v));v∈int(r)},where ˜hr(v)=(2/π)⋅arctan√tan(πhr(v)/2),

the tile associated with and denote it by .

Let be a rectangular diagram of a surface. We define the surface associated with to be the union  of the tiles associated with rectangles from : .

###### Proposition 1.

Let be a rectangular diagram of a surface. Then is a surface with corners in , and we have .

###### Proof.

First consider a single rectangle . The function can be extended continuously and smoothly to except at the vertices of , where it jumps by . The closure of the graph of is a smooth image of an octagon. Its boundary consists of four straight line segments parallel to the sides of and another four straight line segments hanging over the vertices of , see Fig. 7.

Along each of the latter four straight line segments, is tangent to a helicoid that is independent of the size of (i.e. of and ): the tangent plane to at the point , , , is . Tangency with a helicoid is a general property of the graphs of bounded harmonic functions on a polygon that are constant on each side of the polygon and have jumps at corners. Near each corner such a function has a form , where and is a complex coordinate in the plane. The tangency with a helicoid can even be shown to be of the second order.

By composing with the map , which is a monotonic function such that and , we get the function , whose graph  is also a curved octagon with the same boundary as , but now it has an additional property that the tangent plane to  is orthogonal to the -plane along the whole of the boundary . The specific choice of will play an important role in the sequel.

Identification (1) takes to a disc with corners in , which is the tile . Fig. 8 shows a tile projected stereographically into . (The reader is alerted that the ‘coordinate grids’ in Fig. 7, which are added to visualize the surfaces, are not related to that in Fig. 8.) The boundary has exactly two points at each of the circles and , and at these points the tangent plane to is orthogonal to the corresponding circle.

These points will be referred to as the vertices of , and the four arcs of the form , where , which form the boundary of , the sides of .

By construction we also have the following.

###### Lemma 1.

The tile is tangent to the plane field

 (3) ξ−=ker(cos2(πτ/2)dφ−sin2(πτ/2)dθ)

along the sides and , and to the plane field

 (4) ξ+=ker(cos2(πτ/2)dφ+sin2(πτ/2)dθ)

along the sides and .

Let and be two compatible rectangles. If they are disjoint, then either the tiles and are disjoint or they share one or two vertices. In the latter case they have the same tangent plane at the common vertices.

If and share a vertex , say, then and share a side, which is , and all other tiles are disjoint from . The tiles and approach from opposite sides and have the same tangent plane at each point of . Moreover, the intersection has the form , where consists of common vertices of and (one, two, or four of them). Thus, the direction of the tangent plane to has no discontinuity at .

Figure 9 shows the preimages in of two tiles sharing a single side, and the tiles themselves.

Finally, if is a rectangle, then the tiles and are disjoint. Indeed, by construction, at the horizontal sides of one of the functions , vanishes whereas the other is strictly positive, and at the vertical sides of one of these functions equals and the other is strictly less than . Thus, we have for all , and, therefore, the inequality also holds for all by the maximum principle for harmonic functions. Fig. 10 shows the relative position of the graphs of the functions and and the associated tiles in this case.

Thus, in general, intersection of any two tiles , of bounds to the intersection of their boundaries, and the direction of the tangent plane to is continuous on the whole of . It remains to examine the boundary of and to verify that no singularities other than corners occur at .

The boundary of each tile consists of four arcs of the form , where is a vertex of . If is a vertex of two rectangles from , then two tiles of are attached to , so, the interior of is disjoint from . Thus, consists of all the arcs such that is a free vertex of . This implies .

Let be a point in . It corresponds to a longitude of the torus . Let this longitude be and denote it by . The tiles having as a vertex are associated with rectangles of the form or . Let be all such rectangles.

For small enough , the intersections are all pizza slices, and the only our concern is what their union looks like.

Since the rectangles are pairwise compatible, the arcs have pairwise disjoint interiors. The last condition in the definition of a rectangular diagram of a surface guarantees that is either the whole of or a single arc of the form .

In the former case, the union is ‘the whole pizza’, i.e. a disc contained in the interior of . In the latter case, this union is a pizza slice with the angle , , at .

The intersection of with the circle is considered similarly. ∎

###### Remark 3.

Recovering a surface from a rectangular diagram of a surface as described above may look somewhat counterintuitive. Indeed, if is a rectangle, the vertices of the tile correspond to the sides of and the sides of  to the vertices of .

However, as we will see, presentation of surfaces by rectangular diagram is quite practical. In particular, the class of all surfaces of the form is such that each surface in it is uniquely recovered from its torus projection, whose closure is the union .

### 2.4. Orientations

Quite often one needs to endow surfaces and links with an orientation. Here is how to do this in the language of rectangular diagrams.

###### Definition 10.

By an oriented rectangular diagram of a link we mean a pair in which is a rectangular diagram of a link and is an assignment of ‘’ or ‘’ to every vertex so that the endpoints of every edge are assigned different signs. The vertices with ‘’ assigned are referred to as positive and those with ‘’ assigned negative. We also say that is an orientation of .

Every orientation of a rectangular diagram of a link defines an orientation of the link by demanding that increases on the oriented arc whenever is a positive vertex of and decreases otherwise. One can readily see that this gives a one-to-one correspondence between orientations of a rectangular diagram of a link and those of the link associated with it.

###### Remark 4.

From the combinatorial point of view oriented rectangular diagrams of links is the same thing as grid diagrams, with X’s in the latter corresponding to positive vertices and O’s to negative ones.

Now we introduce orientations for rectangular diagrams of surfaces.

The pair of functions is a local coordinate system in the interior of each tile. If two tiles , , say, share a side, then the orientations defined by this system in and disagree at , see Fig. 9. So, it is natural to specify an orientation of a rectangular diagram of a surface as follows.

###### Definition 11.

An oriented rectangular diagram of a surface is a pair in which is a rectangular diagram of a surface and is an assignment ‘’ or ‘’ to every rectangle in so that the signs assigned to any two rectangles sharing a vertex are different. The rectangles with ‘’ assigned are then called positive and the others negative. The assignment is referred to as an orientation of .

Like in the case of links, orientations of any rectangular diagram of a surface are put in one-to-one correspondence with orientations of the surface by demanding being a positively oriented coordinate pair in the tiles corresponding to positive rectangles, and negatively oriented coordinate pair in the tiles corresponding to negative rectangles. In particular, does not admit an orientation if and only if is a non-orientable surface.

In what follows, to simplify the notation, we omit an explicit reference to orientations.

### 2.5. Framings

We will need a slightly more general notion of a framing of a link than the one typically uses in knot theory.

###### Definition 12.

Let be a cusp-free piecewise smooth link in . By a framing of we mean an isotopy class (relative to ) of surfaces with corners such that

1. is a union of pairwise disjoint annuli ;

2. for each , one of the connected components of is a component of and the other is smooth and disjoint from .

If is a framing of a link and is a collection of annuli representing , then we denote by the link . Roughly speaking, is obtained from by shifting along the framing . If is oriented, then is assumed to be oriented coherently with .

We also denote by the linking number , which is clearly an invariant of . If is a smooth knot then framings of are classified by (which is independent on the orientation of the knot).

But if has singularities, a framing contains more information. Indeed, at a singularity of , the tangent plane to any surface with corners such that is prescribed by . So, it cannot be changed by an isotopy of within the class of surfaces with corners.

The surface can approach such a singularity from two sides. Formally, this means that if is a singularity of and is an arc of the form with small enough , then there are two equivalence classes of pizza slices attached to , and the one that the surface realizes is an invariant of the framing.

Let a framing of be fixed. If is another framing of , then the twist of relative to  along any arc connecting two singularities of is a multiple of and is also a topological invariant of .

Clearly, these invariants determine the framing, and there are some obvious restrictions on them, which we need not to discuss.

If is a sublink, then the restriction of a framing is defined in the obvious way. Clearly, any framing of is defined uniquely by its restriction to every connected component of .

###### Definition 13.

If is a surface with corners we call the framing of defined by a collar neighborhood of the boundary framing induced by .

If is a sublink of , where is a surface then we denote by any link contained in such that bounds a collar neighborhood of in .

###### Definition 14.

Let be a rectangular diagram of a link. By a framing of we mean an ordering in each pair of vertices of forming an edge of .

For specifying a framing of a rectangular diagram of a link in a picture we proceed as follows. For every edge , we draw the arc if in the given framing and the arc if . Here by we mean if is a horizontal edge and if is a vertical one. The arcs are assumed to be drawn on , so in the actual planar picture some of these arcs get cut into two pieces, see Fig. 11.

As always, we draw vertical arcs over horizontal ones. The right picture in Fig. 12 shows an example of a framed rectangular diagram of a link.

By definition, any rectangular diagram of a link supports only finitely many framings. They encode framings of the corresponding link in that are not ‘twisted too much’. We now define them formally.

###### Definition 15.

Let be a rectangular diagram of a link. A framing of is called admissible if it can be presented by a surface tangent to one of the plane fields  defined by (3) and (4) at every point .

With every admissible framing of we associate (in general, non-uniquely) a framing of as follows.

Let be a union of annuli that represents an admissible framing of such that at every point the surface is tangent to or . Let be a point from . The tangent plane to at  is orthogonal to the corresponding since so are .

The intersection of with a small ball is a pizza slice, which is equivalent to one of the form or (depending on whether or ), where is the edge of corresponding to , and the equivalence  is given by (1). We denote the pizza slice  by . The framing of associated with is defined on the edge as .

###### Proposition 2.

For a generic , the construction above defines a one-to-one correspondence between admissible framings of and framings of . In general, this correspondence is one-to-many.

###### Proof.

Clearly, we can recover the equivalence classes of the pizza slices from the corresponding framing of , since the only information carried by the pizza slice is from which side it approaches the link . Namely, let and let be the corresponding horizontal edge. Then  is equivalent either to or to , and a choice of one of this options is precisely the information recorded in the framing of . Similarly for vertical edges.

The point now is that, for an admissible framing , the equivalence classes of ’s define completely. Indeed, let be a vertex of and , the endpoints of . At , , the tangent plane to is orthogonal to , and the framing of associated with prescribes from which side the surface approaches .

When traverses the planes and rotate around by and , respectively. Which way the tangent plane to must rotate is determined by and , see Fig. 13. So, the framing  is recovered uniquely.

The only possible reason for the correspondence between framings of and admissible framings of to not be a bijection is a situation when not all points in are singularities of . This occurs when some edges of have ‘length’ , which generically does not happen.

If this does happen, then the tangent plane to a surface representing can rotate freely around at any point that is not a singularity of , so when such a surface is required to be tangent to this does not necessarily prescribe from which side it should approach near . ∎

In the sequel we will assume that all rectangular diagrams of links that we consider are generic, and make no distinction between a framing of a diagram and an admissible framing of the corresponding link.

An obvious but important thing to note here is the following

###### Approximation Principle.

If is a framed rectangular diagram of a link and is the picture of  obtained as described right after Definition 14, then by smoothing near the vertices of we obtain the torus projection of a link of the form , in which the indication of passing over and under at the crossings corresponds to the relative position of the arcs in the -direction: the one with greater is overcrossing, see Fig. 14.

The principle also works in the other way. If is a link disjoint from the circles , then a rectangular diagram of a link such that is isotopic to can be obtained by approximating the torus projection of by the picture of a framed rectangular diagram of a link.

If is a rectangular diagram of a surface, then is tangent to or at every point of the boundary. This together with Approximation Principle implies the following.

###### Proposition 3.

Let be a rectangular diagram of a surface and . The boundary framing on induced by is admissible.

The picture of the corresponding framing of is obtained by connecting each pair of vertices of forming an edge by an arc in covered by the boundaries of the rectangles from , see Fig. 12.

### 2.6. Thurston–Bennequin numbers

Thurston–Bennequin number is a classical invariant of Legendrian links [1]. There are two Legendrian links associated with every rectangular diagram (see [28, 6] and also Section 3 below111The fact that arc-presentations ‘are Legendrian’ was mentioned by W. Menasco to the first present author already in 2003 and has been popularized since then), and their Thurston–Bennequin numbers can be computed from without any reference to the associated Legendrian links as we now describe.

Let be a(n oriented) rectangular diagram of a link. By we denote a diagram obtained from by a small shift in the -direction, i.e. a diagram of the form

 {(θ+ε,φ+ε);(θ,φ)∈R},

where is so small that, whenever is a vertex of , there are no vertices of in the following four regions:

 θ0−ε⩽θ<θ0,θ0<θ⩽θ0+ε,φ0−ε⩽φ<φ0,φ0<φ⩽φ0+ε.

If is oriented, than inherits the orientation from .

Similarly we define by using a shift in the -direction.

###### Definition 16.

Let be an oriented diagram of a link. By the Thurston–Bennequin numbers of we mean the following two linking numbers:

 tb+(R)=lk(ˆR,ˆR↗),tb−(R)=−lk(ˆR,ˆR↖).

These numbers do not change if the orientation of is reversed. So, if is a knot, then the numbers do not depend on the orientation of , and we can speak about Thurston–Bennequin numbers of even if is not oriented.

###### Proposition 4.

(i) Let be an oriented rectangular diagram of a link and a surface with corners in  such that . If is tangent to the plane field defined by (4) (respectively, defined by (3)) at all points of , then is equal to (respectively, to ).

(ii) The following equality holds

 (5) tb+(R)+tb−(R)=−|R|/2,

where denotes the number of vertices in .

(iii) The set

 {⟨f⟩;f is a framing of R}

coincides with .

###### Proof.

Claim (i) follows from the fact that (respectively, ) is obtained from by a small shift in a direction transverse to (respectively, to ).

When traverses an arc of the form , where , the plane  rotates relative to the plane  by the angle . This implies Claim (ii).

We also see, that is maximized (respectively, minimized) over all admissible framings of if it can be presented by a surface with corners such that and is tangent to (respectively, to ) along . Thus for any admissible framing .

Let and . Define a framing as follows. For each horizontal edge of  with the negative vertex and the positive one, we put . Do the same for arbitrarily chosen vertical edges. For the remaining vertical edges put the opposite: .

Let be a surface representing the corresponding admissible framing of . There will be arcs of the form , , along which is tangent to and such arcs along which is tangent to . This implies . So, any integer in the interval can be realized by for a framing of , which completes the proof of Claim (iii). ∎

### 2.7. Which isotopy classes of surfaces can be presented by rectangular diagrams?

The following is a combinatorial definition of the relative Thurston–Bennequin number. The latter appears, e.g. in [19].

###### Definition 17.

Let be an oriented rectangular diagram of a link and a surface (which can be more general than a surface with corners) whose boundary contains . By the Thurston–Bennequin numbers of relative to we call

 tb+(R;F)=tb+(R)−lk(ˆR,ˆRF),tb−(R;F)=tb−(R)+lk(ˆR,ˆRF).

Again, if has a single connected component, then the numbers are independent of the orientation of .

###### Theorem 1.

Let be a rectangular diagram of a link and let be a compact surface in such that each connected component of is either disjoint from or contained in . Then a rectangular diagram of a surface  such that is isotopic to relative to exists if and only any connected component such that , has non-positive Thurston–Bennequin numbers relative to :

 (6) tb+(K,F)⩽0,tb−(K,F)⩽0.

In this theorem is not necessarily assumed to be a surface with corners in the sense of Definition 5, and is allowed to have more general singularities at the boundary, both initially and during the isotopy. This allows to rotate it freely around , even near the singularities of .

###### Proof.

First, we show that condition (6) is necessary. Let be a rectangular diagram of a surface and  a connected component of . By Proposition 3 the boundary framing of  induced by  is admissible.

Therefore, by Proposition 4 for any connected component we have

 lk(ˆK,ˆKF)∈[tb+(K),−tb−(K)],

which is equivalent to (6).

Now assume that (6) holds for any component of . We will use Lemma 2 and Proposition 5 proven below.

The link can have connected components disjoint from . By Lemma 2 we can isotop keeping  fixed so that will have the form for some rectangular diagram of a link . Moreover, we can ensure that the restriction of the boundary framing induced by to any connected component is admissible by making and smaller than and , respectively.

Thus, we may assume without loss of generality that contains (we achieve this by replacing with ). We can now isotop by altering it only in a small neighborhood of so that will become tangent either to or to at every point of .

Application of Proposition 5 with and completes the proof. ∎

###### Lemma 2.

Let be a rectangular diagram of a link, a link disjoint from , and an integer. Then there exists a rectangular diagram of a link such that

1. the link is isotopic to relative to ;

2. for any connected component of we have and .

###### Proof.

To show the existence of without the restrictions on the Thurston–Bennequin numbers we follow the Approximation Principle with a slight modification that now we should avoid intersections with the given link already given in the ‘rectangular’ form.

First, we perturb slightly to make it disjoint from both circles . We may also ensure that the torus projection of has only double transverse self-intersections.

The torus projection of the link is . The torus projection is disjoint from this set, since is disjoint from . Let be the distance between and .

We can now approximate by a framed rectangular diagram of a link in the -neighborhood of . By a small perturbation if necessary we can achieve that the edges of do not appear on the same longitudes or meridians as the edges of . The link will be isotopic to relative to , see Fig. 15.

(The framing that comes with plays no role in the sequel and should be discarded.)

Now if some of the Thurston–Bennequin numbers of connected components of are too large, we apply stabilizations to . Recall (see [5, 6]) that a stabilization of a rectangular diagram is a replacement of a vertex , say, by three vertices such that

1. are vertices of a square of the form ;

2. the square is so small that there are no other vertices of the diagram inside the regions and and there are exactly two vertices at the boundary of each.

We distinguish between type I and type II stabilizations as shown in Fig. 16.

Type I stabilizations preserve and drop by . Type II stabilizations preserve and drop by . So, by applying sufficiently many stabilizations of appropriate types we make the Thurston–Bennequin numbers of all the components of smaller than the given . ∎

For any finite subset , we will use notation in the same sense as for rectangular diagrams:

 ˆX=⋃v∈Xˆv.

If is not a rectangular diagram of a link, then is not a link, but is always a graph, i.e. a -dimensional CW-complex.

The following statement will be given in greater generality than necessary to establish Theorem 1. It will be used in full generality later in the proof of Theorem 2.

###### Proposition 5.

Let be a surface with corners, and two disjoint finite subsets of


text:
changeset 273:a636eda02176

Typo pointed out by Ben Moseley
author Adam Chlipala Sat, 15 May 2010 06:42:05 -0400 19fbda8a8117 806420cf7a2f src/StackMachine.v 1 files changed, 1 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- a/src/StackMachine.v	Wed Apr 28 11:40:03 2010 -0400
+++ b/src/StackMachine.v	Sat May 15 06:42:05 2010 -0400
@@ -618,7 +618,7 @@

(** This function has just a few differences from the denotation functions we saw earlier.  First, [tbinop] is an indexed type, so its indices become additional arguments to [tbinopDenote].  Second, we need to perform a genuine %\textit{%##dependent pattern match##%}% to come up with a definition of this function that type-checks.  In each branch of the [match], we need to use branch-specific information about the indices to [tbinop].  General type inference that takes such information into account is undecidable, so it is often necessary to write annotations, like we see above on the line with [match].

-The [in] annotation restates the type of the term being case-analyzed.  Though we use the same names for the indices as we use in the type of the original argument binder, these are actually fresh variables, and they are %\textit{%##binding occurrences##%}%.  Their scope is the [return] clause.  That is, [arg1], [arg2], and [arg3] are new bound variables bound only within the return clause [typeDenote arg1 -> typeDenote arg2 -> typeDenote res].  By being explicit about the functional relationship between the type indices and the match result, we regain decidable type inference.
+The [in] annotation restates the type of the term being case-analyzed.  Though we use the same names for the indices as we use in the type of the original argument binder, these are actually fresh variables, and they are %\textit{%##binding occurrences##%}%.  Their scope is the [return] clause.  That is, [arg1], [arg2], and [res] are new bound variables bound only within the return clause [typeDenote arg1 -> typeDenote arg2 -> typeDenote res].  By being explicit about the functional relationship between the type indices and the match result, we regain decidable type inference.

In fact, recent Coq versions use some heuristics that can save us the trouble of writing [match] annotations, and those heuristics get the job done in this case.  We can get away with writing just: *)


text:
# The Gaussian beam approximation

The starting point for the approximation of the acoustic field as a Gaussian beam is given by the analytical expression
 (3.1)

where stands for sound speed along a ray trajectory:

and represents the normal to the ray, which can be considered as two-dimensional vector:

such that , where was already defined by Eq.(2.26). In what it follows the projection of sound slowness along will be written as .

While is a real vector both matrices and are complex. Therefore, the complex part of the product induces a Gaussian decay of ray amplitude along the normal (see Fig.3.1), while the real part introduces phase corrections to the travel time along . Additionally, a proper choice of initial conditions for will ensure that det , which frees the Gaussian beam approximation of singularities.

Both components of and can be considered as being dependent of a particular set of local ray parameters, let's say, ray arclength , plus angles and . At any point of the ray one can introduce a set of three orthogonal unit vectors, known as the polarization vectors; naturally, the first polarization vector is ; the other two polarization vectors, which are going to be represented as and , are within the plane perpendicular to (see Fig.3.2).

The vectors and define the possible orientations of and at any coordinate of the ray:

Besides matrices and the Gaussian beam approximation involves two more matrices, called and ; all four matrices are related through the following relationships:

 (3.2)

where
 (3.3)

 (3.4)

and
 (3.5)

where

The components of and correspond to partial derivatives of the ray normal and normal slowness, along the auxiliary parameters and [5]:

Orlando Camargo Rodríguez 2012-06-21


text:
## Statistical Science

### Self-consistency: a fundamental concept in statistics

#### Abstract

The term "self-consistency" was introduced in 1989 by Hastie and Stuetzle to describe the property that each point on a smooth curve or surface is the mean of all points that project orthogonally onto it. We generalize this concept to self-consistent random vectors: a random vector Y is self-consistent for X if $\mathscr{E}[X|Y] = Y$ almost surely. This allows us to construct a unified theoretical basis for principal components, principal curves and surfaces, principal points, principal variables, principal modes of variation and other statistical methods. We provide some general results on self-consistent random variables, give examples, show relationships between the various methods, discuss a related notion of self-consistent estimators and suggest directions for future research.

#### Article information

Source
Statist. Sci., Volume 11, Number 3 (1996), 229-243.

Dates
First available in Project Euclid: 17 September 2002

https://projecteuclid.org/euclid.ss/1032280215

Digital Object Identifier
doi:10.1214/ss/1032280215

Mathematical Reviews number (MathSciNet)
MR1436648

Zentralblatt MATH identifier
0955.62540

#### Citation

Tarpey, Thaddeus; Flury, Bernard. Self-consistency: a fundamental concept in statistics. Statist. Sci. 11 (1996), no. 3, 229--243. doi:10.1214/ss/1032280215. https://projecteuclid.org/euclid.ss/1032280215

#### References

• Anderson, T. W. (1963). Asy mptotic theory for principal component analysis. Ann. Math. Statist. 34 122-148.
• Bandeen-Roche, K. (1994). Resolution of additive mixtures into source components and contributions: a compositional approach. J. Amer. Statist. Assoc. 89 1450-1458.
• Banfield, J. and Raftery, A. (1992). Ice floe identification in satellite images using mathematical morphology and clustering about principal curves. J. Amer. Statist. Assoc. 87 7-16.
• Bickel, P. J. and Doksum, K. A. (1977). Mathematical Statistics. Holden-Day, San Francisco.
• Casella, G. and Berger, R. L. (1990). Statistical Inference. Duxbury Press, Belmont, CA.
• Castro, P. E., Lawton, W. H. and Sy lvestre, E. A. (1986). Principal modes of variation for processes with continuous sample curves. Technometrics 28 329-337.
• Cox, D. R. (1957). Note on grouping. J. Amer. Statist. Assoc. 52 543-547.
• Cox, D. R. and Oakes, D. (1984). Analy sis of Survival Data. Chapman and Hall, New York.
• Cuesta, J. A. and Matran, C. (1988). The strong law of large numbers for k-means and best possible nets of Banach valued random variables. Probab. Theory Related Fields 78 523- 534.
• Dalenius, T. (1950). The problem of optimum stratification. Skandinavisk Aktuarietidskrift 33 203-213.
• Dempster, A. P., Laird, N. M. and Rubin, D. B. (1977). Maximum likelihood estimation from incomplete data via the EM algorithm (with discussion). J. Roy. Statist. Soc. Ser. B 39 1-38.
• Efron, B. (1967). The two sample problem with censored data. Proc. Fifth Berkeley Sy mp. Math. Statist. Probab. 4 831-853. Univ. California Press, Berkeley.
• Eubank, R. L. (1988). Optimal grouping, spacing, stratification, and piecewise constant approximation. SIAM Rev. 30 404- 420.
• Fang, K. and He, S. (1982). The problem of selecting a given number of representative points in a normal population and a generalized Mill's ratio. Technical report, Dept. Statistics, Stanford Univ.
• Fang, K., Kotz, S. and Ng, K. (1990). Sy mmetric Multivariate and Related Distributions. Chapman and Hall, New York.
• Flury, B. (1990). Principal points. Biometrika 77 33-41.
• Flury, B. (1993). Estimation of principal points. J. Roy. Statist. Soc. Ser. C 42 139-151.
• Flury, B. and Tarpey, T. (1993). Representing a large collection of curves: a case for principal points. Amer. Statist. 47 304- 306.
• Friedman, A. (1982). Foundations of Modern Analy sis. Dover, New York.
• Hartigan, J. A. (1975). Clustering Algorithms. Wiley, New York.
• Hastie, T. and Stuetzle, W. (1989). Principal curves. J. Amer. Statist. Assoc. 84 502-516.
• IEEE (1982). IEEE Trans. Inform. Theory 28. (Special issue on quantization.)
• Iy engar, S. and Solomon, H. (1983). Selecting representative points in normal populations. In Recent Advances in Statistics: Papers in Honor of Herman Chernoff on his 60th Birthday (M. H. Rizvi, J. Rustagi and D. Siegmund, eds.) 579-591. Academic Press, New York.
• Jolicoeur, P. (1968). Interval estimation of the slope of the major axis of a bivariate normal distribution in the case of a small sample. Biometrics 24 679-682.
• Jolicoeur, P. and Mosimann, J. E. (1960). Size and shape variation in the painted turtle; a principal component analysis. Growth 24 339-354.
• Kohonen, T. (1995). Self-Organizing Maps. Springer, Berlin.
• Kshirsagar, A. M. (1961). The goodness of fit of a single (nonisotropic) hy pothetical principal component. Biometrika 48 397-407.
• Laird, N. (1988). Self-Consistency. In Ency clopedia of Statistical Sciences, 8 347-351. Wiley, New York.
• Leblanc, M. and Tibshirani, R. (1994). Adaptive principal surfaces. J. Amer. Statist. Assoc. 89 53-64.
• Little, J. and Rubin, D. B. (1987). Statistical Analy sis with Missing Data. Wiley, New York.
• Lloy d, S. (1982). Least squares quantization in PCM. IEEE Trans. Inform. Theory 28 129-149.
• MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proc. Fifth Berkeley Sy mp. Math. Statist. Probab. 3 281-297. Univ. California Press, Berkeley.
• Mallows, C. L. (1961). Latent vectors of random sy mmetric matrices. Biometrika 48 133-149.
• McCabe, G. P. (1984). Principal variables. Technometrics 26 137- 144.
• P¨arna, K. (1990). On the existence and weak convergence of kcentres in Banach spaces. Acta et Commentationes Universitatis Tartuensis 893 17-28.
• Pearson, K. (1901). On lines and planes of closest fit to sy stems of points in space. Philosophical Magazine 2 559-572.
• Pollard, D. (1981). Strong consistency of K-means clustering. Ann. Statist. 9 135-140.
• Rowe, S. (1996). An algorithm for computing principal points with respect to a loss function in the unidimensional case. Statistics and Computing 6 187-190.
• Schott, J. R. (1991). A test for a specific principal component of a correlation matrix. J. Amer. Statist. Assoc. 86 747-751.
• Tarpey, T. (1995). Principal points and self-consistent points of sy mmetric multivariate distributions. J. Multivariate Anal. 53 39-51.
• Tarpey, T. (1996). Self-consistent patterns for sy mmetric, multivariate distributions. Unpublished manuscript.
• Tarpey, T., Li, L. and Flury, B. (1995). Principal points and selfconsistent points of elliptical distributions. Ann. Statist. 23 103-112.
• Tibshirani, R. (1992). Principal curves revisited. Statistics and Computing 2 183-190.
• Ty ler, D. (1983). A class of asy mptotic tests for principal component vectors. Ann. Statist. 11 1243-1250.
• Zopp e, A. (1995). Principal points of univariate continuous distributions. Statistics and Computing 5 127-132.


text:
# Multi-GPU on raw PyTorch with Hugging Face’s Accelerate library

In this article, we examine HuggingFace's Accelerate library for multi-GPU deep learning. We apply Accelerate with PyTorch and show how it can be used to simplify transforming raw PyTorch into code that can be run on a distributed machine system.

8 months ago   •   8 min read

Distributed machine learning is complicated, and when combined with deep learning models that are also complex, it can make just getting anything to work into a research project. Add in setting up your GPU hardware and software, and it may become too much to take on.

Here we show that Hugging Face's Accelerate library removes some of the burden of using a distributed setup, while still allowing you to retain all of your original PyTorch code.

When combined with Paperspace's multi-GPU hardware and their ready-to-go ML runtimes, the Accelerate library makes it much easier to run advanced deep learning models a user may have found difficult before. New possibilities are opened up that might otherwise would go unexplored.

## What is Accelerate?

Accelerate is a library from Hugging Face that simplifies turning PyTorch code for a single GPU into code for multiple GPUs, on single or multiple machines. You can read more about Accelerate on their GitHub repository here.

### Motivation

With state-of-the-art deep learning at the cutting edge, we may not always be able to avoid complexity in the real data or models, but we can reduce the difficulty in running them on GPUs, and on more than one GPU at once.

Several libraries exist to do this, but often they either provide higher-level abstractions that remove fine-grained control from the user, or provide another API interface that needs to be learned first before it can be used.

This is what inspired the motivation of Accelerate: to allow users who need to write fully general PyTorch code to be able to do so, while reducing the burden of running such code in a distributed manner.

Another key capability provided by the library is that a fixed form of code can be run either distributed or not. This is different from the traditional PyTorch distributed launch that has to be changed to go from one to the other, and back again.

## Code changes to use Accelerate

If you need to use fully general PyTorch code, it is likely that you are writing your own training loop for the model.

Training Loop

A typical PyTorch training loop goes something like this:

• Import libraries
• Set device (e.g., GPU)
• Point model to device
• Load dataset using DataLoader (so we can pass batches to the model)
• Train model in loop (once round per epoch):
• Point source data and targets to device
• Calculate output from model
• Calculate loss (e.g., cross-entropy)

There may be other steps too, like data preparation, or running the model on test data, depending on the problem being solved.

Code Changes

In the readme for the Accelerate GitHub repository, the code changes compared to regular PyTorch for a training loop like the above are illustrated, via highlighting of the lines to be changed:

Green means new lines that are added, and red means lines that are removed. We can see how the code corresponds to the training loop steps outlined above, and the changes needed.

At first glance, the changes don't appear to simplify the code much, but if you imagine the red lines are gone, you can see that we are no longer talking about what device we are on (CPU, GPU, etc.). It has been abstracted away, while leaving the rest of the loop intact.

In more detail, the code changes are:

• Import the Accelerator library
• Use the accelerator as the device, which can be CPU or GPU
• Instantiate the model, without having to specify a device
• Setup the model, optimizer, and data to be used by Accelerate
• We don't need to point source data and targets to device
• Accelerator does the backpropagation step

Multi-GPU

The code above is for a single GPU.

On their Hugging Face blog entry, the Accelerate authors then show how PyTorch code needs to be changed to enable multi-GPU using the traditional method.

It includes many more lines of code:

import os
...
from torch.utils.data import DistributedSampler
from torch.nn.parallel import DistributedDataParallel
local_rank = int(os.environ.get("LOCAL_RANK", -1))
...
device = device = torch.device("cuda", local_rank)
...
model = DistributedDataParallel(model)
...
sampler = DistributedSampler(dataset)
...
...
sampler.set_epoch(epoch)
...

The resulting code then no longer works for a single GPU.

In contrast, code using Accelerate already works for multi-GPU, and continues to work for a single GPU as well.

So this sounds great, but how does it work in a full program, and how is it invoked? We will now work through an example on Paperspace to show Accelerate in action.

## Running Accelerate on Paperspace

The Accelerate GitHub repository shows how to run the library, via a well documented set of examples.

Here, we show how to run it on Paperspace, and walk through some of the examples. We assume that you are signed in, and familiar with basic Notebook usage. You will also need to be on a paid subscription so that you can access the terminal.

Paperspace allows you to connect directly to a GitHub repository and use it as a starting point for a project. You can therefore point to the existing Accelerate repository and use it immediately. No need to install PyTorch, or set up a virtual environment first.

To run, start a Notebook in the usual way. Use the PyTorch runtime under the Recommended tab, then scroll to the bottom of the page and toggle Advanced Options. Then, under Advanced Options, change the Workspace URL to the location of the Accelerate repository: https://github.com/huggingface/accelerate . To begin with we are using a single GPU, so the default choice for the machine (P4000) is sufficient. We will proceed to multi-GPU later in this article.

This will start the Notebook with the repo files present in the Files tab on the left-hand navigation bar.

Because the examples supplied with the repo are .py Python scripts, and these work fine on Paperspace in this interface, we don't attempt to show them as a .ipynb notebook here. Although, if you want, the library can be launched from a notebook too.

Let's see the example.

Simple NLP example

Hugging Face was founded on making Natural Language Processing (NLP) easier to access for people, so NLP is an appropriate place to start.

Open a terminal from the left-hand navigation bar:

Then there are a some short setup steps

pip install accelerate
pip install datasets transformers
pip install scipy sklearn

and we can proceed to the example

cd examples
python ./nlp_example.py

This performs fine-tuning training on the well-known BERT transformer model in its base configuration, using the GLUE MRPC dataset concerning whether or not a sentence is a paraphrase of another.

It outputs an accuracy of about 85% and F1 score (combination of precision and recall) of just below 90%. So the performance is decent.

If you navigate to the metrics tab, you can see that the GPU was indeed used:

The script can also be invoked with various arguments to alter behavior. We will mention some of these at the end.

### Multi-GPU

For multi-GPU, the simplifying power of the library Accelerate really starts to show, because the same code as above can be run.

Similarly, on Paperspace, to gain a multi-GPU setup, simply switch machine from the single GPU we have been using to a multi-GPU instance. Paperspace offers multi-GPU instances for A4000s, A5000s, A6000s, and A100s, though this varies from region to region.

Then use the dropdown in the left-hand navigation bar:

to select a multi-GPU machine, and restart:

Changing from P4000 to A4000x2 will work well here.

Note: If you were not already running a single GPU machine, create a Notebook in the same way as for the single GPU case above, but choose an A4000x2 machine instead of the P4000 machine.

Then, to invoke the script for multi-GPU, do:

pip install accelerate datasets transformers scipy sklearn

and run through its brief configuration steps to tell it how to be run here:

accelerate config
In which compute environment are you running? ([0] This machine, [1] AWS (Amazon SageMaker)): 0

Which type of machine are you using? ([0] No distributed training, [1] multi-CPU, [2] multi-GPU, [3] TPU): 2

How many different machines will you use (use more than 1 for multi-node training)? [1]: 1

Do you want to use DeepSpeed? [yes/NO]: no

Do you want to use FullyShardedDataParallel? [yes/NO]: no

How many GPU(s) should be used for distributed training? [1]: 2

Do you wish to use FP16 or BF16 (mixed precision)? [NO/fp16/bf16]: no

Note that we say 1 machine, because our 2 GPUs are on the same machine, but we confirm that 2 GPUs are to be used.

Then we can run as before, now using the launch command instead of python to tell Accelerate to use the config that we just set:

accelerate launch ./nlp_example.py

You can see that both GPUs are being used by running nvidia-smi in the terminal.

### More features

As hinted at by the configuration file setup above, we have only scratched the surface of the library's features.

Some other features that is has include:

Computer vision example

There is also another machine learning example that you can run; it's similar to the NLP task that we have been running here, but for computer vision. It trains a ResNet50 network on the Oxford-IIT Pet Dataset.

On our Notebook, you can add the following to a code cell to quickly run the example:

pip install accelerate datasets transformers scipy sklearn
pip install timm torchvision
cd examples
wget https://www.robots.ox.ac.uk/~vgg/data/pets/data/images.tar.gz
tar -xzf images.tar.gz
python ./cv_example.py --data_dir images

## Conclusions and next steps

We have shown how the Accelerate library from Hugging Face simplifies running PyTorch deep learning models in a distributed manner compared to traditional PyTorch, without removing the fully general nature of the user's code.

Similarly, Paperspace simplifies accessing multi-GPU + PyTorch + Accelerate by providing an environment in which they are ready-to-go.

For some next steps:

### Licensing

Code in the Hugging Face GitHub repository is made available by them under the Apache License 2.0.


text:
Copied to
clipboard

## G = C20⋊6SD16order 320 = 26·5

### 6th semidirect product of C20 and SD16 acting via SD16/C4=C22

Series: Derived Chief Lower central Upper central

 Derived series C1 — C2×C20 — C20⋊6SD16
 Chief series C1 — C5 — C10 — C20 — C2×C20 — C2×D20 — C20⋊4D4 — C20⋊6SD16
 Lower central C5 — C10 — C2×C20 — C20⋊6SD16
 Upper central C1 — C22 — C42 — C4⋊Q8

Generators and relations for C206SD16
G = < a,b,c | a20=b8=c2=1, bab-1=a9, cac=a-1, cbc=b3 >

Subgroups: 702 in 142 conjugacy classes, 51 normal (15 characteristic)
C1, C2, C2, C2, C4, C4, C22, C22, C5, C8, C2×C4, C2×C4, C2×C4, D4, Q8, C23, D5, C10, C10, C42, C4⋊C4, C2×C8, SD16, C2×D4, C2×Q8, C20, C20, D10, C2×C10, C4×C8, C41D4, C4⋊Q8, C2×SD16, C52C8, D20, C2×C20, C2×C20, C2×C20, C5×Q8, C22×D5, C85D4, C2×C52C8, Q8⋊D5, C4×C20, C5×C4⋊C4, C2×D20, C2×D20, Q8×C10, C4×C52C8, C204D4, C2×Q8⋊D5, C5×C4⋊Q8, C206SD16
Quotients: C1, C2, C22, D4, C23, D5, SD16, C2×D4, D10, C41D4, C2×SD16, C5⋊D4, C22×D5, C85D4, Q8⋊D5, D4×D5, C2×C5⋊D4, C20⋊D4, C2×Q8⋊D5, C206SD16

Smallest permutation representation of C206SD16
On 160 points
Generators in S160
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)(21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40)(41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60)(61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80)(81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)(101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120)(121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140)(141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160)
(1 82 123 115 60 35 149 75)(2 91 124 104 41 24 150 64)(3 100 125 113 42 33 151 73)(4 89 126 102 43 22 152 62)(5 98 127 111 44 31 153 71)(6 87 128 120 45 40 154 80)(7 96 129 109 46 29 155 69)(8 85 130 118 47 38 156 78)(9 94 131 107 48 27 157 67)(10 83 132 116 49 36 158 76)(11 92 133 105 50 25 159 65)(12 81 134 114 51 34 160 74)(13 90 135 103 52 23 141 63)(14 99 136 112 53 32 142 72)(15 88 137 101 54 21 143 61)(16 97 138 110 55 30 144 70)(17 86 139 119 56 39 145 79)(18 95 140 108 57 28 146 68)(19 84 121 117 58 37 147 77)(20 93 122 106 59 26 148 66)
(2 20)(3 19)(4 18)(5 17)(6 16)(7 15)(8 14)(9 13)(10 12)(21 69)(22 68)(23 67)(24 66)(25 65)(26 64)(27 63)(28 62)(29 61)(30 80)(31 79)(32 78)(33 77)(34 76)(35 75)(36 74)(37 73)(38 72)(39 71)(40 70)(41 59)(42 58)(43 57)(44 56)(45 55)(46 54)(47 53)(48 52)(49 51)(81 116)(82 115)(83 114)(84 113)(85 112)(86 111)(87 110)(88 109)(89 108)(90 107)(91 106)(92 105)(93 104)(94 103)(95 102)(96 101)(97 120)(98 119)(99 118)(100 117)(121 151)(122 150)(123 149)(124 148)(125 147)(126 146)(127 145)(128 144)(129 143)(130 142)(131 141)(132 160)(133 159)(134 158)(135 157)(136 156)(137 155)(138 154)(139 153)(140 152)

G:=sub<Sym(160)| (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)(21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40)(41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60)(61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80)(81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100)(101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120)(121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140)(141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160), (1,82,123,115,60,35,149,75)(2,91,124,104,41,24,150,64)(3,100,125,113,42,33,151,73)(4,89,126,102,43,22,152,62)(5,98,127,111,44,31,153,71)(6,87,128,120,45,40,154,80)(7,96,129,109,46,29,155,69)(8,85,130,118,47,38,156,78)(9,94,131,107,48,27,157,67)(10,83,132,116,49,36,158,76)(11,92,133,105,50,25,159,65)(12,81,134,114,51,34,160,74)(13,90,135,103,52,23,141,63)(14,99,136,112,53,32,142,72)(15,88,137,101,54,21,143,61)(16,97,138,110,55,30,144,70)(17,86,139,119,56,39,145,79)(18,95,140,108,57,28,146,68)(19,84,121,117,58,37,147,77)(20,93,122,106,59,26,148,66), (2,20)(3,19)(4,18)(5,17)(6,16)(7,15)(8,14)(9,13)(10,12)(21,69)(22,68)(23,67)(24,66)(25,65)(26,64)(27,63)(28,62)(29,61)(30,80)(31,79)(32,78)(33,77)(34,76)(35,75)(36,74)(37,73)(38,72)(39,71)(40,70)(41,59)(42,58)(43,57)(44,56)(45,55)(46,54)(47,53)(48,52)(49,51)(81,116)(82,115)(83,114)(84,113)(85,112)(86,111)(87,110)(88,109)(89,108)(90,107)(91,106)(92,105)(93,104)(94,103)(95,102)(96,101)(97,120)(98,119)(99,118)(100,117)(121,151)(122,150)(123,149)(124,148)(125,147)(126,146)(127,145)(128,144)(129,143)(130,142)(131,141)(132,160)(133,159)(134,158)(135,157)(136,156)(137,155)(138,154)(139,153)(140,152)>;

G:=Group( (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)(21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40)(41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60)(61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80)(81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100)(101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120)(121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140)(141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160), (1,82,123,115,60,35,149,75)(2,91,124,104,41,24,150,64)(3,100,125,113,42,33,151,73)(4,89,126,102,43,22,152,62)(5,98,127,111,44,31,153,71)(6,87,128,120,45,40,154,80)(7,96,129,109,46,29,155,69)(8,85,130,118,47,38,156,78)(9,94,131,107,48,27,157,67)(10,83,132,116,49,36,158,76)(11,92,133,105,50,25,159,65)(12,81,134,114,51,34,160,74)(13,90,135,103,52,23,141,63)(14,99,136,112,53,32,142,72)(15,88,137,101,54,21,143,61)(16,97,138,110,55,30,144,70)(17,86,139,119,56,39,145,79)(18,95,140,108,57,28,146,68)(19,84,121,117,58,37,147,77)(20,93,122,106,59,26,148,66), (2,20)(3,19)(4,18)(5,17)(6,16)(7,15)(8,14)(9,13)(10,12)(21,69)(22,68)(23,67)(24,66)(25,65)(26,64)(27,63)(28,62)(29,61)(30,80)(31,79)(32,78)(33,77)(34,76)(35,75)(36,74)(37,73)(38,72)(39,71)(40,70)(41,59)(42,58)(43,57)(44,56)(45,55)(46,54)(47,53)(48,52)(49,51)(81,116)(82,115)(83,114)(84,113)(85,112)(86,111)(87,110)(88,109)(89,108)(90,107)(91,106)(92,105)(93,104)(94,103)(95,102)(96,101)(97,120)(98,119)(99,118)(100,117)(121,151)(122,150)(123,149)(124,148)(125,147)(126,146)(127,145)(128,144)(129,143)(130,142)(131,141)(132,160)(133,159)(134,158)(135,157)(136,156)(137,155)(138,154)(139,153)(140,152) );

G=PermutationGroup([[(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20),(21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40),(41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60),(61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80),(81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100),(101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120),(121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140),(141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160)], [(1,82,123,115,60,35,149,75),(2,91,124,104,41,24,150,64),(3,100,125,113,42,33,151,73),(4,89,126,102,43,22,152,62),(5,98,127,111,44,31,153,71),(6,87,128,120,45,40,154,80),(7,96,129,109,46,29,155,69),(8,85,130,118,47,38,156,78),(9,94,131,107,48,27,157,67),(10,83,132,116,49,36,158,76),(11,92,133,105,50,25,159,65),(12,81,134,114,51,34,160,74),(13,90,135,103,52,23,141,63),(14,99,136,112,53,32,142,72),(15,88,137,101,54,21,143,61),(16,97,138,110,55,30,144,70),(17,86,139,119,56,39,145,79),(18,95,140,108,57,28,146,68),(19,84,121,117,58,37,147,77),(20,93,122,106,59,26,148,66)], [(2,20),(3,19),(4,18),(5,17),(6,16),(7,15),(8,14),(9,13),(10,12),(21,69),(22,68),(23,67),(24,66),(25,65),(26,64),(27,63),(28,62),(29,61),(30,80),(31,79),(32,78),(33,77),(34,76),(35,75),(36,74),(37,73),(38,72),(39,71),(40,70),(41,59),(42,58),(43,57),(44,56),(45,55),(46,54),(47,53),(48,52),(49,51),(81,116),(82,115),(83,114),(84,113),(85,112),(86,111),(87,110),(88,109),(89,108),(90,107),(91,106),(92,105),(93,104),(94,103),(95,102),(96,101),(97,120),(98,119),(99,118),(100,117),(121,151),(122,150),(123,149),(124,148),(125,147),(126,146),(127,145),(128,144),(129,143),(130,142),(131,141),(132,160),(133,159),(134,158),(135,157),(136,156),(137,155),(138,154),(139,153),(140,152)]])

50 conjugacy classes

 class 1 2A 2B 2C 2D 2E 4A ··· 4F 4G 4H 5A 5B 8A ··· 8H 10A ··· 10F 20A ··· 20L 20M ··· 20T order 1 2 2 2 2 2 4 ··· 4 4 4 5 5 8 ··· 8 10 ··· 10 20 ··· 20 20 ··· 20 size 1 1 1 1 40 40 2 ··· 2 8 8 2 2 10 ··· 10 2 ··· 2 4 ··· 4 8 ··· 8

50 irreducible representations

 dim 1 1 1 1 1 2 2 2 2 2 2 2 4 4 type + + + + + + + + + + + + image C1 C2 C2 C2 C2 D4 D4 D5 SD16 D10 D10 C5⋊D4 Q8⋊D5 D4×D5 kernel C20⋊6SD16 C4×C5⋊2C8 C20⋊4D4 C2×Q8⋊D5 C5×C4⋊Q8 C5⋊2C8 C2×C20 C4⋊Q8 C20 C42 C2×Q8 C2×C4 C4 C4 # reps 1 1 1 4 1 4 2 2 8 2 4 8 8 4

Matrix representation of C206SD16 in GL6(𝔽41)

 40 39 0 0 0 0 1 1 0 0 0 0 0 0 22 10 0 0 0 0 13 19 0 0 0 0 0 0 0 40 0 0 0 0 1 34
,
 0 11 0 0 0 0 15 30 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 7 34 0 0 0 0 1 34
,
 1 0 0 0 0 0 40 40 0 0 0 0 0 0 1 0 0 0 0 0 12 40 0 0 0 0 0 0 34 7 0 0 0 0 40 7

G:=sub<GL(6,GF(41))| [40,1,0,0,0,0,39,1,0,0,0,0,0,0,22,13,0,0,0,0,10,19,0,0,0,0,0,0,0,1,0,0,0,0,40,34],[0,15,0,0,0,0,11,30,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,7,1,0,0,0,0,34,34],[1,40,0,0,0,0,0,40,0,0,0,0,0,0,1,12,0,0,0,0,0,40,0,0,0,0,0,0,34,40,0,0,0,0,7,7] >;

C206SD16 in GAP, Magma, Sage, TeX

C_{20}\rtimes_6{\rm SD}_{16}
% in TeX

G:=Group("C20:6SD16");
// GroupNames label

G:=SmallGroup(320,712);
// by ID

G=gap.SmallGroup(320,712);
# by ID

G:=PCGroup([7,-2,-2,-2,-2,-2,-2,-5,253,120,254,219,184,1123,297,136,12550]);
// Polycyclic

G:=Group<a,b,c|a^20=b^8=c^2=1,b*a*b^-1=a^9,c*a*c=a^-1,c*b*c=b^3>;
// generators/relations

׿
×
𝔽


text:
1. ## maximal volume question mmn 14 3B

V is the volume of a piramid which is created by the plane
$\frac{x}{\sqrt{x_0}}+\frac{y}{\sqrt{y_0}}+\frac{z} {\sqrt{z_0}}=\sqrt{a}$
and the x=0 y=0 z=0 planes

i cant imagine it
how its a piramid
i know that the volme is base multiplied by height/3

but here i just cant see how tho build the formula for it

in the solution they have done some sort of determinant divided by 6
dont know why

2. When y and z are both 0, that equation reduces to $x= \sqrt{ax_0}$. When x and z are both 0, that equation reduces to $y= \sqrt{ay_0}$. When x and y are both 0. that equation reduces to $z= \sqrt{az_0}$. So the plane contains the points $(\sqrt{ax_0}, 0, 0)$, $(0, \sqrt{ay_0}, 0)$ and $(0, 0, \sqrt{az_0})=$.

The "pyramid" has that as base and the xy, xz, and yz planes as sides with (0, 0, 0) as the vertex.

As far as the form of the answer in the book is concerned, they are probably using the fact that the volume of a parallelpiped, formed by three vectors, u, v, w, at one vertex is the "triple product", $u\cdot(v \times w)$. You probably know that the cross procuct of two vectors can be written as a "symbolic" determinant:
$\left|\begin{array}{ccc}i & j & k \\ v_1 & v_2 & v_3 \\ w_1 & w_2 & w_3\end{array}\right|$

The dot product of u with that is
$\left|\begin{array}{ccc}u_1 & u_2 & u_3 \\ v_1 & v_2 & v_3 \\ w_1 & w_2 & w_3\end{array}\right|$

It is not difficult to show, geometrically, that the volume of a "pyramid" (tetrahedron) formed by one corner of a paralellepiped is 1/6 of the volume of the parallelpiped.

3. its been solved by "lagrange conditions"
out condition is
$g(x)=\frac{x}{\sqrt{x_0}}+\frac{y}{\sqrt{y_0}}+\fr ac{z}{\sqrt{z_0}}-\sqrt{a}$

so the zero points are the points when the plane touches the axes.
i dont know what is vertex
but in wikipedia
vertex (plural vertices) is a special kind of point that describes the corners or intersections of geometric shapes.

the question states 4 planes cutting each other creating a paralellepiped some sort of cubic form.
and we need 3 vector comming out of the same vertex to find the volume of the paralellepiped

but our given plane in the formula can make only 2 vectors
because its 2d
i am not sure about the third one

its geometricly impossible to see how from one 2d plane we get 3 points of vectors on the 3d plane

4. its been solved by "lagrange conditions"
out condition is
$g(x)=\frac{x}{\sqrt{x_0}}+\frac{y}{\sqrt{y_0}}+\fr ac{z}{\sqrt{z_0}}-\sqrt{a}$

so the zero points are the points when the plane touches the axes.
i dont know what is vertex
but in wikipedia
vertex (plural vertices) is a special kind of point that describes the corners or intersections of geometric shapes.

the question states 4 planes cutting each other creating a paralellepiped some sort of cubic form.
and we need 3 vector comming out of the same vertex to find the volume of the paralellepiped

but our given plane in the formula can make only 2 vectors
because its 2d
i am not sure about the third one

its geometricly impossible to see how from one 2d plane we get 3 points of vectors on the 3d plane

maybe if the place is tilted downward than from 0,0,0 we get 3 vectors

but the 3d shape in this case is not a paralellepiped

??


text:
# How to compute the residue of a complex function with essential singularity

I'm a student of mechanical engineering and I have a problem with computing residues of a complex function. I've read some useful comments in the other threads. Now I've got some ideas about essential singularity and series expansion in computing the residue. However, I still can't find the solution to my problem. I arrived at a complex function in the process of finding a solution to a mechanical problem. Then I had to obtain the residues to proceed to the next steps. The function has the following form:

$$f(z)=\frac{\exp(Az^N+Bz^{-N})}{z}$$

where $A$, $B$ and $N$ are real constants $(N \geq 3)$.

I want to compute the resiude at $z=0$. I wrote the Laurent series of $f$, but got an infinite sum. I do not even know if I am at the right direction. I would be really thankful if someone could give me a hint on this and put me back in the right direction.

-
I formatted your post in order to make it more readable. I guess you want $N$ to be a natural number, else your $f$ isn't defined in a neighborhood of zero. –  t.b. Jul 8 '11 at 15:24
What do you mean by "I got an infinite sum"? The Laurent series is of course going to be an infiite sum, but I don't think that is what you meant... –  Mariano Suárez-Alvarez Jul 8 '11 at 15:26
@Theo Buehler: Thanks for modification. And as you guessed, N is a natural number (integer). –  Benyamin Gholami Jul 11 '11 at 6:27
@Mariano Suárez-Alvarez♦: You are right. I meant the infinite sum does not converge. However, with the help of friends here I'm at the right direction now. –  Benyamin Gholami Jul 11 '11 at 6:30

From each even term in the exponential series, you get one contribution where the positive and negative powers of $z$ cancel out. This is the middle term of the binomial expansion, and to get the coefficient $a_{-1}$ in the Laurent series you need to sum this over all even terms, which leads to

$$a_{-1}=\sum_{k=0}^\infty\frac1{(2k)!}\binom{2k}{k}A^kB^k=\sum_{k=0}^\infty\frac{(AB)^k}{k!^2}\;.$$

-
Thank you for your answer. –  Benyamin Gholami Jul 11 '11 at 7:47
It's probably worth point out that $\sum w^k/(k!)^2$ is the Bessel function $J_0(2i w)$. en.wikipedia.org/wiki/Bessel_function –  David Speyer Jul 15 '11 at 16:04
@David Speyer: Thank you for your helpful comment. –  Benyamin Gholami Jul 16 '11 at 20:15
@David: Actually, it's more convenient to use the modified Bessel function to represent that series: $I_0(2\sqrt{w})$... –  Ｊ. Ｍ. Jul 17 '11 at 11:28

I'm assuming $N$ is an integer here to avoid issues with branches of the logarithm.

Note that $\exp(Az^N) = \sum_{m=0}^{\infty} {A^mz^{mN} \over m!}$ and $\exp(Bz^{-N}) = \sum_{m=0}^{\infty} {B^mz^{-mN} \over m!}$, so that $\exp(Az^N + Bz^{-N})$ is the product of these two series, and ${\displaystyle{\exp(Az^N + Bz^{-N}) \over z}}$ is the product of these two series divided by $z$.

The residue at $z = 0$ will be the cofficient of the ${1 \over z}$ term in this product divided by $z$, or in other words the constant term in the product. A constant term is obtained in the multiplication when you multiply a term ${A^mz^{mN} \over m!}$ by a term ${B^mz^{-mN} \over m!}$ (with the same $m$). So the constant term in the overall product is the sum of these, that is, $\sum_{m=0}^{\infty} {(AB)^m \over (m!)^2}$ and this will be your residue.

-
Thank you both for your good answers. Your comments really helped. In the process of my solution I arrived at a contour integral. Then I had to use the residue theorem to solve the integral. Also I arrived at another integral with the following format: $$f(z)=\frac{\exp(Az^N+Bz^{-N})}{z-a}$$ where a is a constant and can be in/or out of the closed contour. My problem is that how I should obtain the residue in both cases (when a is in and out of the contour). Can I use the Laurent expansion like the previous problem? How the singularity at z=0 affect the solution? –  Benyamin Gholami Jul 11 '11 at 7:43


text:
## Sunday, January 2, 2011

### Happiness is a Warm Tweet

Often obtaining training labels is a limiting factor for getting things done. Towards this end, Ramage et. al. make an interesting observation regarding Twitter: tweets are rich with annotation corresponding to Twitter conventions. Emoticons, hash-tags, and at-directions provide information about the emotional, semantic, and social content of the tweet.

So for kicks I decided to make a Twitter happiness detector. With a little help from Wikipedia I learned what the common emoticons are for indicating happiness and sadness. For any particular tweet, I called it happy if it contained at least one happy emoticon and no sad emoticons; I called it sad if it contained at least one sad emoticon and no happy emoticons; and otherwise I called it ambiguous. Most tweets are ambiguous, and the goal is to generalize to them; but for training I'll only use the unambiguous tweets.

There are several features in the new vowpal wabbit that come together and make this problem pleasant to attack: support for sparse high-cardinality features; model complexity control via the hashing trick; the --adaptive flag which is like an automated improved tf-idf weighting; native support for n-gram expansion; and of course, the ability to churn through dozens of millions of tweets on my laptop before lunch is over. Training on a week of tweets and testing on a future day of tweets leads to an AUC of 0.87, i.e., given a random happy and sad tweet the resulting regressor is 87% likely to score the happy tweet as more happy than the sad tweet. (Note: one has to remove emoticons when parsing, otherwise, the AUC is 1. The point here is to generalize to ambiguous tweets.) At this point I'm not leveraging the LDA support in vowpal, I'm just encoding each token nominally, so presumably this can be improved.

I took another random sample of 10000 tweets from even further in the future, which turn out to be mostly ambiguous tweets since that is what most tweets are. I then ranked them, and here are the 10 happiest and 10 saddest tweets. Just to reiterate, emoticons are stripped from the tweets during parsing: that several of the happiest and saddest tweets have emoticons in them indicates the ease of predicting emoticon presence from the other tokens in the tweet.

## 10 Happiest Tweets

@WRiTExMiND no doubt! <--guess who I got tht from? Bwahaha anyway doe I like surprising people it's kinda my thing so ur welcome! And hi :)
@skvillain yeh wiz is dope, got his own lil wave poppin! I'm fuccin wid big sean too he signed to kanye label g.o.o.d music
And @pumahbeatz opened for @MarshaAmbrosius & blazed! So proud of him! Go bro! & Marsha was absolutely amazing! Awesome night all around. =)
Awesome! RT @robscoms: Great 24 hours with nephews. Watched Tron, homemade mac & cheese for dinner, Wii, pancakes & Despicable Me this am!
Good Morning 2 U Too RT @mzmonique718: Morningggg twitt birds!...up and getting ready for church...have a good day and LETS GO GIANTS!
Goodmorning #cleveland, have a blessed day stay focused and be productive and thank god for life
AMEN!!!>>>RT @DrSanlare: Daddy looks soooo good!!! God is amazing! To GOD be the glory and victory #TeamJesus Glad I serve an awesome God
AGREED!! RT @ILoveElizCruz: Amen to dat... We're some awesome people! RT @itsVonnell_Mars: @ILoveElizCruz gotta love my sign lol
#word thanks! :) RT @Steph0e: @IBtunes HAppy Birthday love!!! =) still a fan of ya movement... yay you get another year to be dope!!! YES!!
Happy bday isaannRT @isan_coy: Selamatt ulang tahun yaaa RT @Phitz_bow: Selamat siangg RT @isan_coy: Slamat pagiiii

## 10 Saddest Tweets

Migraine, sore throat, cough & stomach pains. Why me God?
Ik moet werken omg !! Ik lig nog in bed en ben zo moe .. Moet alleen opstaan en tis koud buitn :(
I Feel Horrible ' My Voice Is Gone Nd I'm Coughing Every 5 Minutes ' I Hate Feeling Like This :-/
SMFH !!! Stomach Hurting ; Aggy ; Upset ; Tired ;; Madd Mixxy Shyt Yo !
Worrying about my dad got me feeling sick I hate this!! I wish I could solve all these problems but I am only 1 person & can do so much..
Malam2 menggigil+ga bs napas+sakit kepala....badan remuk redam *I miss my husband's hug....#nangismanja#
Waking up with a sore throat = no bueno. Hoping someone didn't get me ill and it's just from sleeping. D:
Aaaa ini tenggorokan gak enak, idung gatel bgt bawaannya pengen bersin terus. Calon2 mau sakit nih -___-
I'm scared of being alone, I can't see to breathe when I am lost in this dream, I need you to hold me?
Why the hell is suzie so afraid of evelyn! Smfh no bitch is gonna hav me scared I dnt see it being possible its not!

## Observations

First, emoticons are universal, which allows this trick to work for many different languages (I think? I can't read some of those).

Second, Twitter data is very clean. Silly ideas like this never worked with web data, because there was always this huge hurdle of separating the content from other parts of the payload (navigational, structural, etc.). In addition web pages are big where tweets are short, so tweets can have a clear emotional tone where web pages might have multiple.

Third, vowpal should be in the list of tools that people try when faced with a text classification problem. This took less than half a day to put together, and most of that was data wrangling.

#### 2 comments:

1. FWIW, Google Translate identified the ones I couldn't read as Indonesian, Dutch, and 2 more Indonesian. I wonder if it's a coincidence that Indonesia used to be (more or less) the Dutch East Indies? And are there that many Indonesian twitterers relative to English-speakers, or are they that much more detectably emotional?

2. The company I'm working for owns several Twitter mobile apps. My Twitter data comes from there, not from Twitter, and I've noticed there is some peculiarities in the data. In particular they have a client which is very popular in Indonesia, so I have a lot of geo tags from that area of the globe.


text:
How specific is the exception of negative charge location (orbital vs atom) for determining stability of conjugate base?

Chapter 3 Acid-base reactions in Klein's Organic Chemistry As a Second Language explains an exception to the typical order of important factors for determining how stable a negative charge on a conjugate base is [1, p. 61]:

This example illustrates that a negative charge on an $$\mathrm{sp}$$ hybridized carbon atom is more stable than a negative charge on an $$\mathrm{sp^3}$$ hybridized nitrogen atom. For this reason, $$\ce{NH2-}$$ can be used as a base to deprotonate a triple bond.

How specific is this exception? Does it only hold true for nitrogen? Or could an oxygen atom be $$\mathrm{sp^3}$$ or $$\mathrm{sp^2}$$ hybridized and still be less stable than the structure on the left despite its higher electronegativity?

Reference

1. Klein, D. R. Organic Chemistry As a Second Language: First Semester Topics, 4th ed.; Wiley: Hoboken, 2016. ISBN 978-1-119-11066-8.
• Exception to typical order is kind of ambiguous. Why isn't this just included in the typical order? In fact, what is the typical order that is listed in this book?
– Zhe
Jul 26 at 15:22

The enhanced electronegativity that comes from having carbon with $$\mathrm{sp}$$-hybridized orbitals is enough to allow terminal acetylenes to protonate nitrogen-anion bases like $$\ce{NH2^-}$$, but (in the absence of additional enhancements such as conjugation) not an oxyanion base like $$\ce{OH^-}$$. In effect carbon with $$\mathrm{sp}$$-hybridized orbitals lies between ordinary nitrogen and oxygen atoms.
We can get the same effect with $$\mathrm{sp^3}$$-hybridized orbitals on carbon in a cyclopentadiene ring, as with the parent compound $$\ce{C5H6}$$ which is an even stronger acid than acetylene. The acidity comes from the ring becoming aromatic when it is deprotonated and negatively charged; as a result cyclopentadiene is weakly deprotonated even by highly concentrated sodium hydroxide solutions, as well as being strongly deprotonated by amide ions. When you study aromaticity you should see this effect, as well as the opposite effect of cyclopropenyl compounds acting as Lewis bases to make that ring aromatic.


text:
Inexact averaged projection algorithm for nonconvex multiple-sets split feasibility problem 待定
Some properties of a class of refined Eulerian polynomials 待定
New exact solutions to the nonlinear Zoomeron equation with local conformable time-fractional derivative 待定
On split $\delta$-Jordan Lie triple systems 待定
A global rigidity theorem for the length of concircular curvature tensor on the locally conformally symmetric Riemannian manifold 待定
Approximate quadratic functional inequality in $\beta$-homogeneous normed spaces 待定
General solutions of a higher order impulsive fractional differential equation involving the Riemann-Liouville fractional derivatives 待定
The number of failed components in a conditional coherent operating system 待定
Directional Preimage Entropy for Z_k 待定
Orthogonality Empirical Likelihood based Inferences for Linear Mixed Effects Models 待定
Application of the alternating direction method for the structure-preserving finite element model updating problem 待定
HIGHER ORDER COMPLEX DIFFERENTIAL EQUATIONS WITH ANALYTIC COEFFICIENTS IN THE UNIT DISC 待定
Piecewise Coons surface reconstruction over arbitrary hierarchical T-meshes 待定
On $\I$-covering mappings and 1-$\I$-covering mappings 待定
Central reflexive rings with an involution 待定
Explicit Iterative Sequences of Positive Solutions for A Class of Fractional Differential Equations on An Infinite Interval 待定
Indefinite Least Squares Problem with Quadratic Constraint and its Condition Numbers∗ 待定