Terms and Tennis Court Link

Some Useful Terms

A Polytope is different from a Polygon, which is a 2-dim figure. A Polytope is defined by as a Convex Hull of a set of vertices or a Cone of a set of halfspaces.

There are two main objects: a H-Polyhedron and V-Polyhedron. The bounded versions are the H-Polytope and the V-polytope.

Of course, there is the cone, which is the homogenized version of a polyhedron.

More about cones:

A Convex Cone can come in many varieties. A Blunt Cone does not contain the origin, while the origin belongs to a Pointed Cone. If the lineality space of a cone has dimension zero, is said to be pointed.

Direct sum

A theorem: The polar of a pointed cone is blunt and vice versa. Surprise, Surprise, this is a Farkas Lemma!!!!

A course in McMaster's that has amazingly beautiful slides on introduction to Polyhedral theory. It is obviously based on Schrijver's book.

---

Lattices and stuff:

Matrix decompositions, also the the polylib-lattices link.

A paper on Hermite Normal form. One of the authors wrote the lattices-and-cryptography-book with Goldwasser.

---

An Affine function is a x --> cx - z for c \in R^d*.
A trace (or trace)
is the weighted sum of the eigen values of the matrix. The weight of an eigen value
being its multiplicity. It is also the sum of the diagonal elements of the matrix. A
graph eigen value is the eigen value of a graph. This the defn. of graph spectrum .
This link also has some info about the eigen value of a graph.
The Caley hamilton theorem about the
characteristic equation.
Also look up the links from the Characteristic Polynomial
A Hadamard matrix is one that has elements from {-1,+1}.
A Hypergraph is a graph in which the edge set is any subset
from the powerset of the set of vertices (A usual graph is a 2-uniform hypergraph).
According to wolfram, a bigraph is the same as a bipartite graph, which
is possibly incorrect. A bigraph has signs on the edges. The proper definition is this?????? Google of bigraph returns bipartite graphs.
So, we need to check up on the definition.

This is a very good introduction to the Ellipsoid method (PDF link).

---

tennis court Read the rest of this entry >>

The Serpent and the Rope

Last updated: 11/05
=============
Due to running into rough weather (laptop disk crash and hand fracture), I was reasonably offline for most of the time. The nice part of that being that I had a chance to read the wonderful book The Serpent and the Rope by Raja Rao a second time. Also, I had a chance to read two comparative studies of works by Raja Rao. The one Shyamala Narayan titled Raja Rao: Man and his works and the one by Makarand Paranjape titled Best of Raja Rao.


begin side note


I have added an excellent biography of Shankara in the sidebar. It is this. It contains one sloka describing the success and glory of life of Adi Sankara:

“Ashta varshe chaturveedi
Dvaadasae sarva saastravit,
Shodasee kritavaan bhaashyam
Dvaatrimsee munirabhyagaat.”

meaning,

“At eight, a master of four Vedas
At twelve, a professor of all sastras,
At sixteen, an interpreter and commentator
At thirty two, a great sage.”

Also, the following biography by kamakoti peetham is good.


end side note.

Though the title and the beginning of the novel give hints that the plot may be Advaitic, no such hints would help the reader through the philosophical musings and metaphysical dilogues in which come as part of the plot. I myself was put off in the previous reading (in Bangalore?) by his sudden change of context, very slow movement of story and other things. Perhaps I was not slow enough then to appreciate such a great book!

The epigraph of the book is the deep Advaitic saying (from Astavakra Gita?):

Waves are nothing but water.
So is the sea
-- Sri Atmananda Guru

Sri Atmananda guru [Sri Krishna Menon] is the Guru of Sri Raja Rao.

Use of other languages in the book

The Serpent and the Rope is an amazing book and Raja Rao's scholarly writing puts me in his awe. He quotes from Sankara (Dakshninamurthy astakam, Kashi Panchakam, Kalabhairava astakam, Annapurna astakam, Manisha panchakam, Nirvana satakam) Bhavabhuthi's Uttararama Charita, Kalidasa's Raghuvamsam, French sources and others.

Purusha Suktam on page 272

In particular, this great (greatest?) author from India seems to have problems in expressing some feelings in English. At the places when words fail the author in English, he uses -- more often than not -- Sanskrit to express the emotion.

Beginning of the book

This is the often quoted beginning of the book:

I was born a Brahmin - that is devoted to Truth and all that. "Brahmin is he who knows Brahman," etc., etc., ... but how many of my ancestors since the excellent Yagnyavalkya, my legendary and Upanishadic ancestor, have really known the Truth excepting the sage Madhava, who founded an empire or, rather helped to build an empire, and wrote some of the most profound of Vedantic texts since Sri Sankara? There were otheres, so I'm told, who left hearth and riverside fields, and wandered to mountains distant and hermitages "to see god face to face." And some of them did see God face to face and built temples. But when they died -- for indeed did they "die" -- they too must have been burnt by tank or grove or meeting of two rivers, and they too must have known they did not die. I can feel them in me, and know they knew they did not die. Who is it that tells me they did not die? Who but me.

So, my ancestors went one by one and were burnt, and their ashes have gone down the rives.

When ever I stand in a river I remember how when young, on the day the monster ate the moon and the day fell into an eclipse, I used til and kusha grass to offer the manes my filial devotion. For withal I was a good Brahmin. I even knew grammar and the Brahma Sutras, read the Upanishads at the age of four, was given the holy thread at seven ...
...

Rama and the place his Advaitic thinking gives to Women in general and Man-Woman relationships in particular

There are a reasonable number of pointers in the book as to where the Advaitic thinking of Rama places Women in general. Also, where do the Man-Woman relationships figure in his thinking.

Some forward pointers of where his marriage is headed to given in one of the first pages (page 26?):

And Yagnavalkya had said to Maitreyi. "For whose sake, verily does a husband love his wife? Not for the sake of his wife, but verily for the sake of Self in her." Did little mother love the Self in my father? Did I love the Self in Madeline? I knew I did not ...

Also, Rama's description of what he feels about Savitri -- when he first meets her -- shows what he expects from a wife:

We had one thing in common: we both knew Sanskrit, and could entertain each other with Uttara Rama Charita or Raghuvamsa.

On pages 57, we get an insight as to what the Advaitic Rama expects from a wife.

It makes all the difference in the world whether the woman of your life is with you or not; she alone enables you to be in a world that is familiar and whole. If it is not his wife, then for an Indian it may be a sister in Mysore, or little Mother in Benares.

Love is a way of way of looking at things. If you love you forget yourself, and percieve the object not as you see it, but rather as seen. The woman therefore is the priestess of God.

The saying by Yagnyavalkya is again used when Rama goes to Cambridge to meet Savitri (page 171)

One cannot possess the world, one can become it: I could not possess Savitri -- I became I. Hence the famous saying of Yagnyavalkya to his wife. "The husband does not love the wife for the wife's sake, the husband loves the wife for the sake of the Self in her."

Second reference to the priestess of God??

(yet to add: stuff about Mother, little-mother, Madeline, Savitri, Lakshmi in Bombay, Lakshmi in Cambridge, Catherine)


Some parts are poetic

Rama and Madeline's pet Bull and the pet Elephant. Also their taking care of them by feeding the "pets". Madeline's saving of the Bull from the old man. Rama thinking that the signs on the Bull make it an auspicious Basavanna.

The symbolic marriage between Rama and Savitri.

Some parts are extremely poignant: The time when Rama takes leave of Madeline:

Devi, Devi ayam paccimas te Ramaciraca padapankajasparchah
Goddess, here for the last time
Does the head of Rama touch the lotus of your feet.

At the end of the novel, there are two upa-kadhas (pitta kadhas in Telugu):

The story of Rama-Deva and the

The story of Radha, Krishna and Durvasa.

Story of Radha, Brahmachari-Krishna, Upavasi-Durvasa

The story involving Radha, Krishna and Durvasa is a very interesting one, explaining a fundamental concept of Advaita: namely illusiory nature of the world. Here is the story:

"One day Radha had a very possessive thought of Krishna. 'My Krishna,' She said to herself, as though one could possess Krishna as one could possess a calf, a jewel. Krishna, the Absolute Itself, immediately knew her thought. And when the absolute knows, the knowing itself, as it were, is the action of the act; things do not happen according to his wish, but his wish itself is his own creation of his wish, as the action is the creation of his own action.

"So, Durvasa the great Sage was announced.
...

The full story is here.

The original story is also excerpted here.

The women of Vraja once asked Lord Krishna to name some Brahmin to whom they could offer food. Lord Krishna named “Durvasa”. The Gopis asked: “How can we approach him? There is the Yamuna which is in floods. How are we to cross it? Name some other Mahatma, please”. The Lord said “Request Yamuna in the name of Nitya Brahmachari Krishna to give way and it will instantly do so. The Gopis were amused, and though sceptic, did as requested and lo! the river at once gave way for the perplexed Gopis to cross it; Yamuna indeed knew the real Svarupa of Krishna, the spotless divine purity that He was! He was a Nitya Brahmacharin.

What amazes me -- besides the story itself -- is the story telling power of Raja Rao. Raja Rao added spice (and other ingredients) and explained the story so beautifully that the vivid images of the story and the moral stick permanently in the mind!

To continue the thoughts of Rama after the story:

To be free is to know one is free, beyond the body and beyond the mind; to love is to know one is love, to be pure is to know one is purity. Impurity is in action and reaction: what is born must die, what has form must vanish and stink. ....
....

Benares is everywhere where you are, says an old Vedantic text, and all waters are the Ganges. ...
...

Other than that, the concept of illusory nature of the world is experienced by Rama in the whole book. In fact, in pages 340?? Rama says to Madeline

"The world is either unreal or real -- the serpent or the rope. There is no in-between-the-two -- and all that's in between is poetry, is sainthood ... "

As Shyamala Narayan pointed out aptly in her book, The Serpent and the Rope begins and ends with the definition of a Brahmin. In the latter, some humor is added by giving another definition.

...
"Do you know what a Brahmin is, Catherine?"

"No, what is it?" She came back, having gone halfway to the kitchen.

"A Brahmin is he who knows Brahman. That is one definition," I said. "There is another rouguish definition. A Brahmin is he who loves a good banquet."

"You certainly do not belong to the second category, poor dear. Rama, what shall we do when you are gone? You have become so like one of us. We will be lost."

Georges looked at me. He looked so sad.

"We must have been brothers in a past life."
...

The roughish definition Raja Rao is hinting at is Brahmanah bhojana priyah. Rama can now afford to laugh at the two definitions as he has found a Guru and is on the path to realization.



Makarand Paranjape says the following about the book:

Published twenty two after Kanthapura, The Serpent and the Rope is the Rao's most appreciated work. If the former is modelled on a Upapurana, the latter is a kind of Mahapurana or epic: geographically, historically, philosophically and formally, its sweep is truly epical.

Raja Rao as a part of the Original Trinity of Indian English Authors

It is well known that the trinity of Raja Rao, R.K.Narayan and Mulk Raj Anand are the pioneers of Indian english writing in the form of novels.

Later, Makarand Paranjape goes into controversial area by comparing Raja Rao with R.K.Narayan and Mulk Raj Anand and (nearly) calling them trite. I agree however with his observation that Raja Rao is more scholarly when compared to others. I used to once agree with him on the former point. What happened was that, in the midst of a heated conversation I too called R.K Narayan names. This is surprising considering that I had read almost all his major works. After reading Raja Rao, I prefer Raja Rao to R.K.Narayan. I would not mind R.K.Narayan when asked to make a choice between him and other Indian authors. He is good. He is simple. He may be too simple.

The Cat and the Shakespeare is said to be the book where Raja Rao shows that the Absolute can be approached through play (as in The Cat and the Shakespeare) as effectively as through ascetic meditation (as in The Serpent and the Rope).

yet to add:

Rama and fear?

second place of reference woman priestess of the God???

Argument between Rama and Georges pages 108-112 about truth.

The two times when Rama feels he took a bath in Ganges: when he wins an argument with Georges and when Catherine tells him that she and Georges are going to have a baby(340-341?).

...
"I have news to give you," said Georges, pursuing his own thoughts, and playing with a knife on the table. He w as silent for a brief moment, looked at Catherine with adoration and announced: "Catherine will have a baby in five or six months. You are first person to know it, Rama."

To this day I cannot tell you why, but I felt somewhere I had been washed clean and whole by the Ganges, dipped again and again and made shining with Shravan Saturday sun. I must have looked very moved, for Catherine put the soup in front of me, touched my head as Saroja might have and said:
"You will look after him, when he grows up, and give him all your wisdom, won't you?"
...

I am reading The Great Indian Way, a biography of Mahatma Gandhi by Raja Rao. The beginning is very good and exceeds expectations.
Read the rest of this entry >>

Unbounded polyhedral domains and computability of SUREs

Problem: Give a single theorem that characterizes the theorems 1, corollaries 1/2 and skewed variations of corollaries 1/2. In other words, give a characterization of the computability of an SURE defined over an arbitrary polyhedral unbounded domain.

Explanation: The domain could be

F_n (as in theorem 1),

strip of the type Q_t* F_(n-t) (as in corollary 1/2)

a skew of the domain of collorary 1/2

a conical subset of F_n through the origin

a minkowski sum of a polytope and a cone (meaning, an arbitrary polyhedron which is a subset of F_n)


The statement of computability may be the following:

An SURE defined over an arbitrary unbounded polyhedral domain is incomputable iff

it has a cycle C of weight W(C)

-W(C) belongs to the characteristic cone of the domain.

Some assumptions

The SURE is defined as ... V_j(z-w_j)

The SURE is defined in all the integral (or rational points) in the domain

The RDG is strongly connected. We can do a greedy index splitting (ala Allan-Kennedy???)


We have two cones

C1: The dependence cone: constructed with the negative dependence vectors

C2: The characteristic (or recesssion) cone of the domain. This should have a vector other than {0} as the domain is assumed to be unbounded.

The convex cone of the (negative) dependence vectors strictly contains all the vectors which are the weight of cycles. Also, containing vectors just means of the same direction It could contain vectors which cannot be expressed by cycles of the weight vectors.

What has the separability of these two cones have to do with computability?: If C1 and C2 are separable, then of course the SURE is computable.

A sufficient condition for computability: If there exists a cycle whose weight is a vector that belongs to the two cones, then the SURE is incomputable. The weight vector of a cycle ofcourse belongs to a cycle. Does it belong to the char.cone of the domain?

How does the computability condition of SURE change if the domains are non-polyhedral, but still convex?
The concept of char.cone is from polyhedral domains. According to the book and lecture notes of Bertsekas et.al, the concept is perfectly valid in every convex domains. There are some caveats though. ????

Notes about importance of computability problem of S*RE's defined on unbounded Vs. bounded domains. According to QS, Unbounded domains are not that important while bounded domain are. This is because, they are more common. I disagree with this. More importantly, however, QS make the important observation that the computability problem of bounded domains is equivalent to the testing of the acyclicity of the EDG. From the outside, this seems like a condition which can be applied only to a non-parametrtized domain. However, thinking of the parameters as additional dimensions is a standard trick.
So, the question is given a bounded domain, and a computation defined over it, what is the computability problem?

Problem: An SURE defined over a bounded domain is computable iff, there exists no zero weight cycle.

Restatement of the problem: Given a partially integral polytope -- meaning some vertices are integral, others are rational -- find whether the polytope contains the vertex {0}

Algorithm:Use KMW decomposition. Find which edges donot participate in any cycle, remove them, recurse on the rest of the graph.


Question on finitizabilty of the domains

Later note:
I had originally defined the finitizability so the the computability condition of COR.1/2 of KMW can be applied to the case of SUREs defined over the skewed domains of COR.1/2.
Later note: With the precison we have for the condition for computability, we donot need this "finitizability".

Question: Given a computation defined over an unbounded polyhedral domain.
To find: A skew of the domain such that the application of which results in the maximization of for loops.

The number of finizable dimensions

the skewing matrix which can do this

A listing of the dimensions which are finitizable


Example1: if given a computation defined over Q_t * F_(n-t) (ala domain of cor.1/2 of KMW), we should give

a value of 2, meaning 1 out of the 2 domains is "finitizable"

The identity matrix: I_(2*2)

a listing of the domains which are finitizable: meaning j

Example2: If the domain of the computation is a skew of the domain of COR.1/2 of KMW, thr output should be

a value of 1, meaning 1 out of 2 domains are finitizable

a proper skew

a listing of the domains Read the rest of this entry >>