Introduction to Ashtavakra Gita

Once upon a time there was a student of the scriptures. He would work hard all day every day and then read aloud the holy language of sacred verses late into the night. His wife, round of belly with their coming child, would sit beside him in the dim room, listening as her weary beloved chanted the ancient words.

One late night in her eighth month a voice from inside her belly said to the father: "Sir, please be attentive – you are mispronouncing that verse." Tired and short-tempered, without thinking why he would feel so enraged at being corrected by an unborn child, the father cursed the voice- and because the father had built up merit, his curse took hold: the child was born deformed, with eight crooks in his body. That child was called Ashtavakra, a name which means `eight bends'. Everyone who saw him laughed in derision.

That crippled child was an enlightened master who took birth in this family to reveal in simple words the essence of mystical experience. Janaka, king of the known world, father of the bride of God, Sita, daughter of the earth, that very King Janaka became this crippled boy's disciple. The book based on that event is called The Song of the Eightfold Cripple, or Ashtavakra Gita.

Asthavakra was not keen on accepting students, and so had few. When King Janaka came to hear of the wisdom of the crippled child he approached the boy as a humble student, not a commanding king. The boy accepted the king instantly as his disciple. This caused some talk in the sangham. ~Ah, Ashtavakra does have favorites after all, he accepted the king without any of the trials he had all of us face!~ This grumbling became a quiet force, and Ashtavakra knew of it.

One day the King was late and so the boy delayed his discourse. The moment the king arrived, Ashtavakra spoke: `This day I have had a vision, the capitol city will erupt in terrible fires and earthquakes- all there will die. Those who have loved ones or valuables there must hurry now if they wish to save anything!'

All the monks left. As the dust settled, only the boy and the king were sitting. The boy said softly, `Great king, is there nothing you would save?` Janaka replied, ~My lord and my friend, you are my only treasure.~ The cripple nodded and softly said, ~Well then if I am indeed your treasure, mount your horse now and go and gather my students back to me, tell them I have been mistaken, the capitol city is in no danger. Take your horse, and go.~

Rising to do as bidden, the King put his foot into the stirrup, and as he swung up over the saddle, realization dawned in his mind. He swallowed, looked about him at this new earth, heard new birds singing for the first time, and then looked at the cripple at his feet. The two looked at one another, and then the king left to find the other students.

Once back, the other students grumbled at being sent about here and there on foolish errands. One or two howeverd did soon understand why the master had chosen the king as a student in his own way.

This is what was said that day, as all sat about and heard these words of nectarine wisdom. Read the rest of this entry >>

Aryan Invasion Theory, Amitav Ghosh

Now, even the BBC link seems to say so. As if someone believed in it! (link via santosh on the advaitin mailing list)

Amitav Ghosh write a very powerful and moving essay about the 1984 riots (link via Amit Verma).

Incidentally, Amitav Ghosh seems to be quite an interesting author. He is a recipient of the annual award by the Gyanpeeth (Is it the same as The Gyanpeeth award?).
==
updated (11/22)
Some very good suggestions on teaching about Hinduism by Rosser. Link by Shadow Warrior. Read the rest of this entry >>

Translations by Swami Krishnanada

The Divine Life Society has lots of ebooks of Vedantic texts. The translations are done by Swami Krishnananda. The translation of BrahmaSutras (PDF link) has a very informative introduction of the schools of Indian philosophy (darsana) and also of the view points of the Acharyas who wrote commentaries of the BrahmaSutras.

The BrahmaSutras are part of the prasthatraya, the three sacred texts. It is said that a person wishing to start a new school of thought must write commentaries on the prasthanatraya as every Vedantic school builds from these. The prasthanatraya consist of the Upanishads (srutis, or revelation), the Bhagavad Gita (being the most important text of the smriti, recollection) and the BrahmaSutras (being of the category sutra, system).

The word sutra itself is etymologically related to sew and thread and hence means some kind of memory aid between different texts or thoughts. The sutra from Vedantic schools does not mean sutra the way Buddhist schools mean it. The BrahmaSutras are said to be terse and initially seem to contain contradictory thoughts. Swami Krishnananda says the following about them:

Sutras are concise aphorisms. They give the essence of the arguments on a topic. Maximum of thought is compressed or condensed into these Sutras in as few words as possible. It is easy to remember them. Great intellectual people only, with realisation, can compose Sutras. They are clues or aids to memory. They cannot be understood without a lucid commentary (Bhashya). The commentary also is in need of further elaborate explanation. Thus the interpretations of the Sutras gave rise to various kinds of literary writings such as Vrittis (gloss) and Karikas. The different Acharyas (founders of different schools of thought) have given their own interpretations of the Sutras to establish their own doctrines. The Bhashya of Sri Sankara on Brahma Sutras is known as Sariraka Bhashya. His school of thought is Kevala Advaita. The Bhashya of Sri Ramanuja who founded the Visishtadvaita School is called Sri Bhashya. The commentary of Sri Nimbarkacharya is known as Vedanta- parijata-saurabha. Sri Vallabhacharya expounded his system of philosophy of Suddhadvaita (pure monism) and his commentary on the Brahma Sutras is known as Anu Bhashya.

Also the following about the need to write commentaries on the classical texts:

Those who wish to study the philosophy of Vedanta should study the Ten Classical Upanishads and the Brahma Sutras. All Acharyas have commented on Brahma Sutras. This is a great authority for every philosophical school in India. If any Acharya wishes to establish his own cult or sect or school of thought he will have to write a commentary of his own on Brahma Sutras. Then only it will be recognised.

Writing the commentaries on the PrasthanaTraya started from Sri Adi Sankara, who started the Kevala Advaitic school. Sri Swami Krishnananda uses the term uncompromising monism, though I think Advaita or non-dualism is possibly a better word. The following is also from the introduction.

According to Sri Sankara, there is one Absolute Brahman who is Sat-chit-ananda, who is of an absolutely homogeneous nature. The appearance of this world is due to Maya - the illusory power of Brahman which is neither Sat nor Asat. This world is unreal. This world is a Vivarta or apparent modification through Maya. Brahman appears as this universe through Maya. Brahman is the only reality. The individual soul has limited himself through Avidya and identification with the body and other vehicles. Through his selfish actions he enjoys the fruits of his actions. He becomes the actor and enjoyer. He regards himself as atomic and as an agent on account of Avidya or the limiting Antahkarana. The individual soul becomes identical with Brahman when his Avidya is destroyed. In reality Jiva is all-pervading and identical with Brahman. Isvara or Saguna Brahman is a product of Maya. Worship of Isvara leads to Krama Mukti. The pious devotees (the knowers of Saguna Brahman) go to Brahmaloka and attain final release through highest knowledge. They do not return to this world. They attain the Nirguna Brahman at the end of the cycle. Knowledge of Nirguna Brahman is the only means of liberation. The knowers of Nirguna Brahman attain immediate final release or Sadyomukti. They need not go by the path of gods or the path of Devayana. They merge themselves in Para Brahman. They do not go to any Loka or world. Sri Sankara’s Brahman is Nirvisesha Brahman (Impersonal Absolute) without attributes.

Read the rest of this entry >>

Who can show the right way?

Al (of advai.blogspot.com) was intent on proving to a certain community that their thinking of "their way to God is the only way" may not be right. I asked him to stop doing so, as no ordinary person can tell another what the right way is. Also, there is a futility in trying to convince a person who is unwilling to listen.

Initially it seems that, no ordinary man can show us the right way. We feel that we are atleast better that the multitudes who did not even begin their search for realization. So we feel that, only a realized soul, one who is somehow special, can lead us. So most of the quests for realization begin with a search for the Guru. The goal is clear: the Guru, or the Prophet, can lead us by some kind of magic. (This thought is also echoed in the last pages of the The Serpent and the Rope by Raja Rao.)

After some time, it also becomes apparent that, a realized soul cannot show a man the right way, if the man is unwilling to listen, or see things with an open mind. If one realized soul cannot show a man the right way, another realized soul cannot. This is because, no realized soul is greater than another.

It also become apparent that, when a man is willing to see the point and is doing effort to search for the truth, he does not need a realized soul to show him the right way. The right way manifests itself, as it was before him all the time. The moment a man is willing to search for the truth, there comes a time when his veil of ignorance automatically falls off. A realization dawns that a Guru is not doing some magic, but helping to remove the veil.

The where the purpose of a Guru is to just quicken the process. A Guru can reduce the amount of time a yearning soul has to spend in the searching. The purpose of Ishwara is also similar. As Ishwara has control on Maya, He too quicken the process. When I say an Ishwara, I mean the different manifestations of higher powers. They could be from the six Indian theistic schools. Or, they could be the Judeo-Christian-Islamic God.

Hence the sayings of Vivekananda: God is very merciful to those whom He sees struggling heart and soul for spiritual realization. But remain idle, without any struggle, and you will see that His grace will never come.

So, once we understand all this, we have a couple of questions:

What is the right thing for an ordinary man to do with respect to his realization: Should he search for a Guru or not? Should he pray to Ishwara or not?

What is the right thing for an ordinary man to do for the realization of his peers? Should he give them the insights he got? If so, how is he to know whether they are right or wrong? Should he correct them when he feels they are wrong? How does he know for sure whether he is right or wrong? from Plato: What is Good and What is bad, do we need someone to tell us Phaedrus?

What is the right thing for a realized man to do? Is this a trick question? A realized man is beyond right and wrong. What can a realized man do for others' realization? Just guide them, if he wants to.

The Maya of a person can be removed only by Ishwara. Can the Avidya of a person can be removed by a Guru? Possibly. The distinction between Maya and Avidya is possibly quite subtle, as it has caused considerable discussion among the disciples of Sri Adi Sankara. So I will not confuse the picture by posting on them now. Read the rest of this entry >>

Dalai Lama on Science vs. Religion

As a Op-Ed Contributor on the NYTimes, in an article titled Our Faith in Science, His Holiness Dalai Lama (who signs the article as Tenzin Gyatso) has the following to say about religion and science:

If science proves some belief of Buddhism wrong, then Buddhism will have to change. In my view, science and Buddhism share a search for the truth and for understanding reality. By learning from science about aspects of reality where its understanding may be more advanced, I believe that Buddhism enriches its own worldview.

==
Later update (11/14): Also see the letters to the editor in which a writer points out the following:

Instead of focusing on whom to hate and what to fear, these leaders would do well to turn their attention to those "principles we share as human beings" about which the Dalai Lama writes so eloquently.

I am not a Buddhist, but I cannot help noticing how often it is the Buddhists who remind us that we do not have to demonize others in our own search for what is good.

Read the rest of this entry >>

Thoughts about the AUEE deparment

In an excellent post, SJ recounts some of the experiences he had in the EE department of AU. That is, when the department was in its heydays. I cannot agree with the post more. Read the rest of this entry >>

On Having No Head: Douglas Harding

I have read the book On Having No Head: Zen and the Rediscovery of the Obvious by Douglas Harding, sometime back. Like many Zen concepts, the title is both mysterious and informative at the same time.

This very short book (120 pages: with 12pt font and 1.5 spacing) talks about the experience of realization by Douglas Harding. It (the concept of realization) is explained to a modern day human being with western background using the simplest of Buddhist -- mainly from Zen -- concepts. As the title implies, the essence is in "experiencing" headlessness, with the emphasis on experience. Just like many Zen koans, the book carries the essence in the first few pages. All these reasons make the descriptions in the book simple and striking.

Though I am yet to read the book completely, I felt I need not push myself to do so. I found that couple of first chapters contain the crux of the experience of the author. (This is probably why I could not push myself to complete the book.) I also feel that the two ways of experiencing realization are when you experience zero (shunyata) or you experience infinity (purnata).

The following is the first chapter. I found that there is no point highlighting some part of the text. The text is very short, cohesive and all the text is equally important.

The best day of my life -- my rebirthday, so to speak -- was when I found I had no head. This is not a literary gambit, a witticism designed to arouse interest at any cost. I mean in in all seriousness: I have no head.

It was when I was was thirty-three that I made the discovery. Though it certainly came out of the blue, it did so in response to an urgent inquiry; I had for several months had been absorbed in the question: what am I? The fact that I happened to be walking in the Himalayas at the time probably had little to do with it; though in that country unusual states of mind are said to come more easily. However that may be, a very still, clear day, and a view from the ridge where I stood over misty blue valleys to the highest mountain range in the world, made a setting worthy of the grandest vision.

What actually happened was something absurdly simple and unspectacular: just for the moment I stopped thinking. Reason and imagination and all mental chatter died down. For once, words really failed me. I forgot my name, my humaneness, my thingness, all that could be called me or mine. Past and future dropped away. It was as if I had been born at that instant, brand new, mindless, innocent of all memories. There existed only the Now, that present moment and what was clearly given in it. To look was enough. And what I found was khakhi sleeves, terminating sideways in a pair of pink hands, and a khaki shirtfront terminating upwards in -- absolutely nothing whatever! Certainly not a head.

It took me no time at all to notice that this nothing, this hole, where a head should have been, was no ordinary vacancy, no mere nothing. On the contrary, it was very much occupied. It was a vast emptiness vastly filled, a nothing that found room for everthing -- room for grass, trees, shadowy distant hills, and far above them snow-peaks like a row of angular clouds riding the blue sky. I had lost a head and gained a world.

It was all, quite literally, breathtaking. I seemed to stop breathing altogether, absorbed in the Given. Here it was; this superb scene, brightly shining in the clear air, alone and unsupported, mysteriously suspended in the void, and (and this was the real miracle, the wonder and delight) utterly free of "me", unstained by any observer. Its total presence was my total absence, body and soul. Lighter that air, clearer that glass, altogether released from myself, I was nowhere around.

Yet in spite of the magical and uncanny quality of this vision, it was no dream, no esoteric revelation. Quite the reverse: it felt like a sudden waking from the sleep of ordinary life, an end to dreaming. It was self-luminous reality for once swept clean of all obscuring mind. It was the revelation, at long last, of the perfectly obvious. It was a lucid moment in a confused life-history. It was a ceasing to ignore something which (since early childhood at any rate) I had always been busy or clever or too sacred to see. It was naked, uncritical attention to what had all along been staring at my face -- my utter facelessness. In short, it was all perfectly simple and plain and straightforward, beyond argument, thought, and words. There arose no questions, no reference beyond the experience itself, but only peace and quiet joy, and the sensation of having dropped an intolerable burden.

In the next chapters, Harding takes the concept further and gives vivid details of what happened to him after experiencing headlessness. Also he explains various levels of headless ways. The website The Headless way also has nice information about the experience. The videos are also good.

The following are a set of good "koanistic" quotations from the book:

• Suppose a man were all of a sudden to make his appearance here and cut your head off with a sword! -- HUI-CHUNG
  
• Behead yourself! ... Dissolve your whole body into Vision: become seeing, seeing, seeing! -- RUMI
  
• My Soul has been carried away, and usually my head as well, without my being able to prevent it. --ST.TERESA
  
• Cover your breast with nothingness, and draw over your head the robe of non-existence. --ATTAR
  
• Give yourself utterly ... Even though the head itself must be given, why should you weep over it? --KABIR
  
• Seeing into Nothingness - this is the true seeing, the eternal seeing. -- SHEN-HUI
  
• "I think I'll go and meet her," said Alice ... "You can't possibly do that," said the Rose. "I should advise you to walk the other way." This sounded nonsense to Alice, so she said nothing but set off at once towards the Red Queen. To her surprise, she lost sight of her in a moment. -- Through the Looking Glass.
  
• The soul has now no awareness of the body and will give herself no foreign name, not man, not living being, nor anything at all. -- Plotinus
  
• After the body has been cast off to a distance like a corpse, the Sage never attaches himself to it. -- Sankara
  
• If one opens one's eyes and seeks the body, it is not to be found anymore. This is called: In the empry chamber it grows light. Inside and outside, everything is equally light. That is a very favorable sign. -- The secret of the Golden flower.
  
• Vow to acheive the perfect understanding that the illusory body is like dew and lightning. Zen Master Hsu Yun (on his death-bed, in 1959)
  

Read the rest of this entry >>

Happy Birthday, Raja Rao!

Raja Rao (08-November-1908 to ?) would be 98 years today. Arguably, he is one of the greatest Indian English authors. He ranks along with Mulk Raj Anand and R.K.Narayan and the three are aptly called the original trinity. The next generation of Indian English writing had to wait for around 20-30 years till Salman Rushdie appeared. The comparision between Raja Rao with Salman Rushdie is reasonable. A better comparision of Raja Rao could be with James Joyce, as both of them created a new way of writing and then expressed themselves excellently in the new way.



His way of writing is unique. The punctuation itself is so close to the the way Indians talk and think. The following, from the preface of his first novel Kanthapura, explains about his way of writing.

...
The telling has not been easy. One has to convey in a language that is not one's own the spirit that is one's own.
...
After the language the next problem is that of style. The tempo of Indian life must be infused into our English expression, even as the tempo of American or Irish life has gone into the making of theirs. We, in India, think quickly, we talk quickly, and when we move, we move quickly. There must be something in the sun of India that makes us rush and tumble and run on. And our paths are interminable. The Mahabharatha has 214,778 verses and the Ramayana 48,000. The Puranas are endless and innumerable. We have neither punctutation nor the treacherous "ats" and "ons" to bother us -- we tell one interminable tale. Episode follows episode, and when our thoughts stop our breath stops, and we move on to another thought. This was and still is the ordinary style of our storytelling....
...

Beyond the use of language in style and punctuation, his scholarly way of writing can put people in his awe. I would like to think that if Sri. Sarvepalli Radhakrishnan would be a novelist, he would write the way Raja Rao. Raja Rao's careful use of Advaitic concepts in The Serpent and the Rope makes it, what Arvind Sharma calls, India's most famous Advaitic novel.

Some biography snippets from the preface of Makarand Paranjape's book.

Raja Rao was born in an ancient and respected Brahmin family in Hassan, Karnataka, on 8th November, 1908. The eldest son in a family of two brothers and seven sisters, he was the centre of the family.
...

The Introduction chapter in the book by Shyamala Narayan gives another date of birth (the text also implies that there has been a confusion regarding the year of birth too). The following is the relevant excerpt from the book.

Raja Rao was born in Hassan, a small town in the state of Mysore (now called Karnataka). There is some confusion about Raja Rao's date of birth: his books mention it as 1909, but he was actually born on November 5, 1908, as M.K.Naik clarifies. There is an interesting story about his birth. He was born at the precise moment when his father was receiving the Maharaja, Krishna Raja Wodeyar of Mysore, at their house, So the child was called Raja and not Ramakrishna, after his grandfather. Raja Rao comes from a family of Brahmins who had been Vedantins and advisors to kings for generations. He was greatly influenced by his grandfather at Hassan, who taught him to love Sanskrit and kindled his interest in Indian Philosophy.
...

The date of birth given in the following link link also agrees with the one given by Makarand Paranjape.

Raja Rao was born on November 8, 1908 in Hassan, in the state of Mysore in south India, into a well-known Brahman family. ...
...

Autobiographical rant:

He has been of huge influence on me. My first memories of any of his works was looking at his classic book The Serpent and the Rope in my home. The cover had a picture of a beautiful European lady. Behind her was a dark man from India with a cigaratte in his hand. The background to this picture was the waters of Benares. It was one of the books that my mother used in her M.A (literature) and had since become part of the family library.

In one of the first classes of first year of engineering, one of our professors, Prof. P.V.Ratnam, who I admire a lot, had suggested us to read this book. I came home and started it right away "I was born a Brahmin. Brahmin is one who knows Brahman and all that..." The magic in the words, however, could not force me to read beyond a couple of pages and so I kept it aside. However, the book was never far away from me or my personal cupboard. I did not keep the the book away probably because I thought this was just a book like M.G.Say or Clayton-Hancock or Van Valkenburg (the classic books of EE) which needed a couple of careful readings to understand it. Alas, it did not occur to me that to understand the book, all that was needed was a mature reader. Also, that the book was recommended by Ratnam-garu made it a top of the list book.

I intuitively understood that, being unable to understand beyond a couple of pages of a novel which presupposes a good understanding of my beliefs is a serious deficiency on my part.

In the summer vacation between first and second years, I had read a couple of novels mostly R.K.Narayan (quite a few of them) and Serpent and the Rope.

When I went for higher studies to Bangalore, this was one of the books that I took with me -- inspite of the fact that I knew I may not have much time for novels -- mainly because I felt that this book had some magic in it. I was enchanted by the first lines.

Later in Bangalore, when I was in a book reading spree, I began Raja Rao with earnst. This time, I did some research and began with Kanthapura. Next I read The Serpent and the Rope. This time, the words in the book started to make sense. I continued and completed the novel. I also read another novel, The Cat and the Shakespeare. When I left to US, I still had my mother's copy with me. I read the book in the summer of 2003. I donot think I read it again in the next two years.

I began with a earnst study of Advaita as such and had read Deutsch, Arvind Sharma and some books on Ramana Maharishi.

In the Sep, OCT-2005, when I had a fracture of the hand and my movement was restricted, I read the book again, and the book made lot of sense and I could understand many of the quotations and monologues.
Read the rest of this entry >>

How not to still the mind

Once King Janaka was sitting on the bank of a river, repeating 'SOHAM' mantra at the top of his voice.

Sage Astavakra was passing by. The sage was a knower of truth and an enlightened being. He was surprised why king Janaka was chanting the mantra in this loud fashion.

Astavakra wanted to instruct King Janaka the proper way of chanting a mantra. So, he sat down near King Janaka and chanting loudly, :' "This is my Alms Bowl and this is my Yoga Stick " so much so that Astavakra's chanting drowned the chanting of Janaka's chanting!

Now, King Janaka , not to be left behind starting chanting his 'SOHAM' mantra even louder --- this went on for some time -both vyeing with each other in this 'mantra recitation'. ...

Now, King Janaka got really annoyed and asked Asthavakra what the sage was doing. The sage replied "I am repeating - this is my Alms bowl, this is my yoga stick".

King Janaka replied, " Have you lost your mind? Who told you that the Alms bowl and the stick do not belong to you ? Why do you have to keep shouting about it.?"

Sage Astavakra replied , " O Mighty King ! It seems to me you are the one who lacks understanding. who told you that you are not 'THAT '? Why do you to go on shouting that 'I AM THAT' ? 'SOHAM' ?

When king Janaka heard this, he suddenly realized the trut. He understood that he need not go on repeating 'SoHam' mantra , he only needed to understand it and practice 'living' it!

'You are really unbound and actionless, self-illuminating and spotless already. The cause of your bondage is that you are still resorting to stilling the mind.' -- Ashtavakra Gita 1.15 Read the rest of this entry >>

Story of Sudhama as narrated by Raja Rao

The princes of Kathiawar, like the Rajputs everywhere, claimed their descent from the sun and the moon, and belonged to the clan of Sri Rama (the Ikshavakus) or of Sri Krishna (the Yadavs). For, after all, Dwaraka was just around the corner of the peninsula, and that was where Sri Krishna ruled, so that most of the princes of course belonged to the Yadavas, or so they believed. Remember, Sri Krishna married his wife Rukmini at Madhavpur, and that is just down the curve of the bay, and the Yadavs once (and remember too) on that fateful day when they went gambolling to the sacred city of Prabhas Patan and got into a fist-fight, and then to a brawl and then to a real battle, they sent for Sri Krishna.


But he was not to be found -- he'd so planned as to go and lie under a tree (and had not Gandhari cursed that the race of Sri Krishna come to an end) -- and a hunter took Sri Krishna's heel for the head of a deer, and the greatest of Indians thus played the game of even death. He had planned it all, so everything happened according to his intent -- for, for him intent and action were just experience, there was none to act, as it were for he was in action as inaction and in inaction as action.

And so too was that other game of Sri Krishna. He had, while at school, a poor Brahmin companion, Sudhama was his name and he was raggedly miserable. Life had been most ungenerous to him (again it was Sri Krishna's game) -- Sudhama had a wife with a tongue of charcoal cinders and hair made as of rough hemp. When she called, even the street dogs would thgink it was one if their kind talking, and they started answering back. But Sudhama was so patient; he would always speak, when humiliated by his wife, of his friend Sri Krishna who ruled in Dwaraka. "Fine thing to have such a friend. But what does he do for you, you son of tamarind tree hag."

Hearing this morning after morning, Sudhama said one day to his wife: "I go and see Sri Krishna today, this very day."

"Oh yes you will go, you and your cononut-head and bursted-bleak belly, and seeing your tousled hair and bent back and bamboo limbs, even the guards will laugh at you."

"Perhaps you're right," said Sudhama, "but give me please a handful of puffed rice and a piece of molass."

"What for?" She asked.

"Well, when ones goes to see someone, you don't ever go empty handed, do you?"

"A beggar," declared Sudhama's wife, "has no manners," as the buffalo have no courtesies."

"Well, so be it. Give what puffed rice and molass you have to me."

Cursing her stars for such a rice miserable destiny -- that even the little puffed rice she had, she had perforce to give part of it away -- she threw a handful of it to Sudhama's dhoti-edge, broke a piece of molass from the pot, and said with wide-fingered threatening hands: "And don't you come back plain-handed, you cononut-head, after all this. I'll howl till the very spirits in the crematoriums will be frightened. Let's see what your great friend Sri Krishna is going to proclaim and perform for you. I take the name of God and tell you he will have chased out of city."

Sudhama was so accustomed to his wife's tongue and breath, it was as if he heard sound but not meaningful speech. He picked his stick from the corner, and taking the thought of Sri Krishna, he started towards holy Dwaraka. Long was the road to Dwaraka, but such sweetness of love, the trees seemed to open up and spread wide-limbed shade, and cool breezes blew from the northern mountains, and the sea seemed to churn in fervered joy. For when you take the thought of Lord true, all things that seek him rejoice in your rejoicement -- they also wave up and swell with your joy. Sudhama arrived at the city gates and these opened themeselves as if by vestal deities, and even the palace guards did not seem to mind his looks.

"Could you tell His Highness," he begged, "the Lord of Lords, his poor school fellow, the Brahmin Sudhama is at the door?"

"Be so kind as to wait here, Pundit Sir," said the guard politely, and "I'll go tell the Chamberlain."

It was all as if the gods were playing a trick, the Chamberlain seemed just waiting for this event at the door, and Sri Krishna himself, when he heard the news, he had such joy, people could see tears run down his lotus eyes. "Prepare," he commanded, "water to wash my guest's feet." And as Sri Krishna clad in silken blue, his eyes clear as sleep, his gait as if made by the curvature of form when he stood, the washing-stool before him, there he appeared across the courtyard, Sudhama, his boyhood friend. In their high niches the pigeons and parrots began to coo, and the ladies peered from the top apartments at this wondrous happening [You can see this in many a Rajput miniature today.]. Krishna bade Sudhama stand on the ivory stool, and rich with jugs of silver swan-shapen and filled with water, first warm and then cold, and when these were thrown on the Brahmin's withered and dusty feet -- then did Krishna taking the silken hand-cloth from Chamberlain's arm, wipe the friends feet himself. Now Sri Krishna took his friend to the marbled court and before all his noblemen, he said, "Friend, be seated," and showed Sudhama the throne. Could a poor Brahmin occupy such an august seat? No. He would not. Krishna himself sat on a couch beside his friend. They now spoke to each other of all that happened and passed by since their boyhood. They wept and laughed but all around there was as if a wall of luminescent silence. Everything moved in the palace as usual, the noblemen retired to their afternoon siesta, the servants moved with agility and calm, from corner to corner of the palace, the nine diurnal musics sounded, the elephants trumpeted after a good feed, the cows lowed for their returning calves, and when the evening fell a great banquet was laid for the poor Brahmin, Sudhama and he ate as if he was eating his own food, at his home. For, for the first time he was at home himself. Krishna enjoyed munching the puffed rice his friend had brought, and some of it was sent upstairs to Rukmini, and all the palace was given bits of it. It tasted, did this puffed rice, as nothing one has tasted before. It had the delicate saffron smell of Sri Krishna himself. And when the night drums sounded and the meal was over, the hands were washed, the betel leaves served, a carriage was made ready, and beneath the high chandeliers, flower and fruit hangings, as Sri Krishna said farewell to his friend, he embraced him again and again, and they wept. Yes, Sudhama had to go. He had now to go back home. But he'd forgot his promise to his wife. He had asked nothing of Sri Krishna., Pray what can you ask of a friend who is King?

Yet Sudhama was so happy the very mind-picture of Sri Krishna brought him to tears. And when he came nearer and nearer his home, he began however to have fits of fearfulness. What would it be like coming back plain handed? But when the town came it was all a different -- the very walls were shining as if white-washed and much repaired, and when his carriage stopped, his wife stood, a gold plate in her hands, flowers and Kumkum water floating in it, and lighting the lamp of auspiciousness, she welcomed her lord befittingly, and fell at his withered feet. And from that day onwards the city came to be called Sudhamaputi, or the city of Sudhama, but due to the crookedness of people's speech, it became Puri, and later someone added bunder[Bunder means harbour, haven] to it so that today it's called Porbandar, Haven-city.
Read the rest of this entry >>

Mahavakyas of Advaita or Vedanta

The Mahavakyas -- or great sayings or principal statements -- from Upanishads are said to contain the essence of the teachings of Upanishads. It is said that meditating on the Mahavakyas would lead someone towards realization.

Pranava (Aum): Pranava is said to be the fundamental (true) Mahavakya of the Vedas as established in Chapter Twelve. (details?)

For a particular Vedantic system, some of the Mahavakyas are considered more important than the others. This is inspite of the fact that all schools in Vedanta accept Upanishads and all the Mahavakyas are from the Upanishads.

According to Arvind Sharma, Sri Adi Sankara stated that four Mahavakyas are fundamental for Advaitic learning. A web search also shows that Sri Adi Sankara set up the four schools, one for each Mahavakya. (Yet to find out which school stands for which Mahavakya.) They are the following:

1. Sarvam Khalvidam Brahma: meaning All this verily Brahman. This is from Chandogya Upanisad, 3.14.1.
   
   
2. Aham Brahmasmi: I am Brahman. This is from Brhad-aranyaka Upanisad, 1.4.10.
   
   
3. Ayam Atma Brahma The Self is Brahman or This Atman is Brahman. This is from ?
   
   
4. Tat tvam asi: That thou art. This Mahavakya is from Chandogya Upanisad, 6.8.7 (Tat tvam asi svetaketo, "O Svetaketo, you are that")
   
   

Additional Mahavakas from Vedanta. Some of them are:

Prajnanam Brahma: Brahman is Supreme Knowledge prajnanam brahma, This is from Aitareya Upanisad, 1.5.3.

So'ham: He am I. This is from ?? Read the rest of this entry >>

Story of Radha, Brahmachari-Krishna and Upavasi-Durvasa: Raja Rao

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.

"He is on the other side of the river, Lord", spake the messengers, and "and he sends his deep respects".

Then Krishna went into the deep chambers and said to Radha, "Radha, Durvasa the great Sage is come, my dear. We must feed him".

"Oh, then I will cook the food myself" said Radha, and Krishna was very happy at this thought. So he went back to the Hall of Audience, and not long after, Radha came in with all the cooked food. "Yes, the meal is ready my Lord. And I will take it myself to Sage Durvasa".

"Wonderful, wonderful!" exclaimed Sri Krishna, pleased with the devotion of his wife to the Sages.

"I'll go and come," said Radha, and hardly had she gone to the palace door when she remembered the Jumna was in flood. No ferryman would go across. She came back to Krishna and begged, "My Lord, how can I take the food? the river is in flood".

"Tell the river," answered Krishna, "Krishna the brahmachari [The celibate, or who has taken the vow of celibacy] wishes that the way be made for you to pass through."

And Radha went light of heart, but suddenly bethought herself it was a lie. Who better than she to know whether Krishna be brahmachari or not? "Ah the noble lie, the noble lie," she said to herself, and when she came to the river, she said, "Krishna, the Lord, the brahmachari, wishes that way be made for me to pass through".

And of course the river rose high and stood still, but suddenly opened out a blue lane, small as a village footpath, through which Radha walked to the other side. And coming to the opposite shore, she thanked the river, and saluting the great Sage Durvasa, in many a manner of courtesies and words of welcome, spread the leaf and laid him the food.

Durvasa was mighty hungry and he ate the food as though the palm of his hand went down his gullet. "Ah, ah," he said and belched and made himself happy, with curds and rice and many meats, perfumed and spiced with saffron, and when there was nothing left in leaf or vessel, he rose, went to the river and washed his hands. Radha took the vessels to the waters, too to wash, threw the leaf into the Jumna and stood there to leave. Then it was she who remembered, the river was in flood. Sri Krishna had told her what to say while going and not what to utter while coming back.

Durvasa understood her question before she asked - for the sages have this power too -- and he said, "Tell the river, Durvasa the eternal upavasi [He who fasts] says to the river, 'Open and let Radha pass through to the other shore.'"

Radha obeyed but she was more sorrowful. "I have seen him eat till his palm enter his gullet, and he has belched and passed his hand over his belly with satisfaction. It is a lie, a big lie," she said, but she went to the river thoughtful, very thoughtful. "River," she said, "Durvasa who is ever in upavasa says open and let me pass."

And the river opened a lane just as wide as a village pathway, and the waves held themselves over the head, and would not move. She came to the other shore and returned to the palace in heavy distress. "Yes, nature is a lie, nature believes and obeys lies. Lord, what a world," She said to herself and going into the Hall of Sorrowing, shut herself and began to sob. "Lord, what a lie the world is, what a lie."

Sri Krishna knew the cause and cadence of this all, and gently entered the Hall of Sorrowing. "Beloved, why might you be in sorrow?" he said.

"My Lord," she answered, "the river believes you are a brahmachari, and after all who should deny it better than me, your wife? and then I go to Durvasa and he eats with his palm going down his gullet, and he says, "Tell the river, Durvasa who is ever in upavasa asks you to open and let Radha pass." And the river opens herself, makes a way large as a village pathway, and I pass over to this side. The world is a fib, a misnomer, a lie."

"The world, my dear, is not a lie, it is an illusion. Besides, tell me, is my body your husband, Radha?"

"No, my Lord."

"Is my mind your husband, Radha?"

"No, my Lord."

"Then what is it when you say to yourself, 'Krishna, my husband?'"

"Assuredly something beyond the body and beyond the mind -- the Principle."

"And tell me, my love, can you possess that, can you possess it?"

"No, my lord, how can I possess the Absolute? The I is the Absolute." And she fell at the feet and understood, and lived ever after in the light of the Truth.
Read the rest of this entry >>

Illusion

Via Atanu, A very very cool illusion!! It is difficult to believe what is it that we see. Read the rest of this entry >>

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 >>

Cornuejols book: Combinatorial Optimization

I had been reading this book on and off. Very nice presentation, just like the other books -- like Tarjan's book -- in the series by CBMS-NSF.

The interesting part is the material in chapter 6, which talks about {0,+1,-1} matrices. The picture on page 50 gives the relationship between the classes of {0,+1,-1} matrices. The four classes used in the book are PERFECT, IDEAL, BALANCED and TOTALLY UNIMODULAR. A balanced matrix is both perfect and ideal. The set of matrices which are TUM is a (strict) subset of balanced matrices.

I had talked in a couple of posts about TUM matrices. The posts are here. In this post we will see the generalizations of TUM matrices.

Let n(A) be a function which takes a {0,+1,-1} matrix and returns a column vector whose ith component is the number of -1's in the ith column of A.

Now, compare Ax and 1 - n(A) for some x in {0,1}^n. If

the former wins, we have a ideal matrix --> COVERING

the latter wins, we have a perfect matrix --> PACKING (how is it related to perfect graphs?)

if they are tied, we have a balanced matrix.
--
Refer to the matrix (on page 61) which is called the 0,1 extension of a {0,+1,-1} matrix.
--
A bipartite graph is said to be a perfect graph. What about directed bipartite graphs?
The book uses the term bigraph. According to wolfram, a bigraph is the same as a bipartite graph, which is possibly incorrect. A bigraph has signs on the edges.
--

Partially integral Polytopes: Our incidence matrix induces a polytope. We donot know if the vertices of this polytope are integral or not. The dimensions of this polytope is d. However, this polytope is not as important as the polytope of (n+d) dimensions. The interesting things is, this (n+d) dim polytope is partially integral, as the n vertices always induce integral vertices (IS THIS RIGHT???) the question remaining, what about the d vertices? Read the rest of this entry >>

Schrijver's book, Tardos result, and {0,+1,-1} matrices

Schrijver's book has a chapter 15 which is titled Further polynomiality results in linear programming. In that chapter, he covers some additional methods of solution -- as opposed to well known results by Khachiyan, Karmarkar and others -- to the LP problem. The additional results being Megiddo's result, Tardos result. My post on Megiddo's result is this. The result by by Tardos (corollary 15.3a of the book) is significant as it gives a characterization of {0,+1,-1} matrices. It is in pages 195-199 of Schrijver's book. Also, Megiddo's result follows in pages 199-204. The following is the statement we are interested in:

Corollary 15.3a: Tardos result states that there exists a strongly polynomial time algorithm for rational LP problems with {0,+1,-1} constraint matrix.
Intuition: The intuition for this corollary is pretty clear: Khachiyan's method is a polynomial time algorithm, but not strictly polynomial time algorithm. The running time of Khachiyan's algorithm -- for a problem of the type Ax <= b -- is dependent on not just the size of the matrix A, meaning the number of rows and columns of A, but also the number of bits used in encoding the matrix A. OTOH, when we restrict the matrix A to be a {0,+1,-1} matrix, which means we are operating in the unary mode, Khachiyan's algorithm takes strictly polynomial time.

The other contribution of Tardos is that the running time of Khachiyan's algorithm takes time independent of either the size of b or the number of bits used in encoding b. This is as important contribution, as we can reduce the problem complexity to that of a homogeneous system.

Look up if Schrijver's new book has any more information on the same.
What does Schrijver's books says about hypergraphs??

Schrijver's new book also has lot of information on these questions. esp. in chapters 21,24 etc.

--
Are we searching for multi commodity flows? Read the rest of this entry >>

Srimad Bhagavata-anta

In a previous post, I had briefly compared Datta-Atreya and Suka. In this post we will see the how in the 12th chapter of Srimad-Bhagavatha, Datta-Atreya teaches the essence of Advaita.

First an explanation on the title of the post. The interpretation of Upanishads being referred to as Vedanta is quite well known. The title Bhagavatha-anta can also be interpreted as the following: Suka and Vyasa have come to a conclusion in Bhagavatha. What follows in chapter 12 is the essence of their conclusion.

Srimad-Bhagavatha also is well known for its many discrete, and sometimes contradicting schools of thought. More notes is here. As explained in the previous post, the conclusion of the Bhagavatha can be thought of the highly theistic chapters of 10 and 11, where the story of Lord Krishna is explained. In chapter 12, however, there is the advaitic conclusion of the Bhagavatha as explained to Uddhava by Lord Krishna himself. The dialogue seems to happen at the time when Lord Krishna is about to leave his material body.

Avadhutha refers to how the learnt all he wanted to from the world itself. He sites 24 examples (I am sure this 24 has got a metaphorical meaning: like number of letters in Gayathri-Mantra) of his learnings from the world. He gives simple examples of teachings which emphasize detachement, etc. This is a post about the 24 teachings Avadhuta explained to Yadu. Read the rest of this entry >>

Ray Miller's Memoirs

The link to a function at UMD to commemorate the career of Ray Miller is this. The following is the introduction to the function:

Prof. Ray Miller, who retired from our department in 2002, is truly one of the pioneers of the field of computer science. He has had three successful careers – the first at IBM, where he helped build one of the world’s foremost computer science research programs and worked with many of the other leading theoretical computer scientists of his generation – people like Dick Karp, Shmuel Winograd and Nick Pippinger. Ray then had a second career at Georgia Tech,
...

This is a picture of Karp and Miller. The following "relevant part" is excerpted from pages 25-26 of memoirs of Ray Miller (a PDF link):

Upon returning to IBM Research from Cal Tech in the summer of 1963 I was ready to look into some new areas of research. Thus, it was quite appealing when Herman Goldstine, the Director of the Mathematical Sciences Department, suggested to Dick Karp, Sam Winograd, Larry Horwitz and me that looking into parallel computation might be of some interest. Even though this was long before parallel computation was on the minds of many, there was already a clear indication that parallelism could be used to speed up some special purpose computational tasks. IBM had a product developed for the oil industry called the "convolver box". This was a special purpose device that could be attached to the main bus of an IBM computer to do convolutions very rapidly. Convolution was used extensively in oil exploration for the analysis of soundings taken over land and sea to show the deep structure of the earth layers and expose potential locations where oil might be found. With this suggestion we started to look at parallel computation. We designed approaches, algorithms and designs, for many different special purpose computations: parenthesis checking, macro-instruction execution, the Cooley-Tukey convolution algorithm, and others. Our design for the Cooley-Tukey algorithm even rated a footnote in their original paper "An Algorithm for the Machine Computation of Complex Fourier Series" in Mathematics of Computation, April 1965. We published a paper in JACM on uniform recurrence equations that described how parallelism could be used to speed up the numerical computation of systems of differential equations. After a while, the designing of parallel algorithms for these various tasks seemed to be getting quite repetitive to Dick Karp and me, and this led us to realize that there was a hidden approach that we seemed to be using over and over. We formulated this underlying structure, which we called "computation graphs" and published the paper, "Properties of a Model of Parallel Computations: Determinacy, Termination, Queueing" in the SIAM Journal of November 1966. In 1966 this was the only SIAM Journal, but now they publish a number of journals in specialized areas. Computation graphs proved to be quite effective for designing inner loops of computations, but were limited in not 25 having more general computation structures, such as conditional branching, that were needed for more general computations. This led us to a more general model that we termed, "Parallel Program Schemata". We wrote a long paper about these schemata which was finally published in JCSS in May 1969. I continued to work on parallelism even though Dick Karp decided to leave IBM to become a faculty member at Berkeley with a joint appointment in computer science and operations research. I thought it was quite surprising that Dick left IBM at that time because within only a few more months he would have had 10 years service with IBM and thus been vested for retirement benefiets. I wrote another paper on parallel program schemata that discussed some undecidability results based on a schema not possessing the property that we called "repetition freeness", and this paper was published in the first issue of the SIAM Journal of Computing in March 1972.

Read the rest of this entry >>

Tell a story

It was the campus of the top graduate school of India. Raj and Ram were walking together, back to their hostel rooms. They were good friends and had endured the hard first semester together. They thought they knew everything about each other.

The time now was 2am. They had just submitted their programming assigment at 11:59pm of the previous day, before the dmidnight deadline. Then they started their next assignment which was due this weekend.

They were both tired. Cold breeze was blowing at that time in the beautiful campus of Bangalore. They were in their second semester of their stay. They both had to pass an All India entrance test and get the top ranks to get into the computer science department of the top graduate school in India.

Suddenly Raj said "I saw that girl again today, she was wearing the same offensive t-shirt 1". Though Ram was quite sleepy to respond, he asked, "So you named the t-shirt1?". They were talking about a girl they used to notice sometimes a Girl who used to sit next to them sometimes in the Common labs.

The common labs used to have students from people other than computer science department too. Not many of Computer science students wanted to go to that lab. The reason was that the machines were slow. It was kind of prestige question for CS students to sit in a common lab with students of other departmens. Some of these students were noisy and came to the labs only to have fun. Most importanlty, many of the machines there were running Microsoft aka MACRO-SLOW. The CS labs on the other hand were quite and ran the revolutionary OS linux and most of the students there were sober.

This night, both Ram and Raj has started late. So their own labs were full and they had to sit in the common lab.

Ram asked, "What were you saying about the t-shirt?" Raj responded "I have named the t-shirt 'Do you think that ' as t-shirt 1. Also I have named 'CS graduates are .... '. Ram asked, I thought you were too busy doing the assignment to notice the t-shirts of others, leave alone of girls.

Raj said, "I couldnot help but notice the t-shirt when I was helping fix her code". This was too much for Ram. He surely thought Raj was making this up. They both used to talk like drunken guys, without any aim on their way back to hostels on such days.

The next afternoon, they met at the college cafe. They both had missed the morning breakfast. After they were done with eeating it hungrily, Ram asked "yesterday were you saying you helped that Girl?" Raj said, "Oh yeah, and I asked her name. and I asked where she was from and ...". Ram said "ok. ok. we can makeup stories later. How is yor assignement going?" It is fine, I have to.

Ram said, "I am sure you are making this up. I know you and how you behave. I am very sure that you did not talk a single word with that girl till now." Raj said, with his tongue in cheek "I know that you still think me to be a studious guy coming from a all boys engineering college. I bet that I talked to that girl."

Ram got enraged "If you prove it to me that you talked to that Girl, I promise to be cleanly shaven for 1 month". Ram was quite infamous among his classmates to for his unshaven face. "and, if you cannot prove it within the next week, you will not shave for the next 1 month". Neither of them, or any of their classmates minded unshaven faces, as everyone in the school was busy with atleast 5 courses in a semester.

The next day, they were discussing their assignment in the common longue of the library. Ram, with just noticed that the girl passed by. He acted as if he did not notice the girl. Raj too noticed that the girl. He stood up and called softly, "Hello Kusum". Ram was taken aback! "Hi! said Kusum" coming to them. "Kusum, this is my close friend, Ram". "Hello Ram", said Kusum. "So, you are wearing a new tshirt today is it?" said Raj. "Yes" said the girl. May I know what is behind? luckily for Ram, who was still in a state of shock, she was not wearing a coat over the tshirt which covered her back. She turned around. The tshirt read "CS graduates are very boring". She turned back again, said "My day is made, I told the truth atleast on the faces of two nerds today". "See you both later. bye" and she vanished. Raj winked at Ram.

=============
Next act.
=============

An year later, the wedding was in Calcutta in the east. Ram was one of the special invitees. Kusum was from the .......

Bombay in the west, Calcutta in the east, Meerut in the north and Cochin in the extreme south west. Ram and Raj were in a southern city, but quite far from the city in which Kusum's was originally from. This was a truly cross-indian marriage with all the different cultures. To satisfy both the parents, Raj and Kusum had two weddings. The major one was in Raj's home in East. The minor one was in the ancestral home of the girl in south west. The boy and girl, after the marriage went and stayed for some time in the boy's parents house in Meerut in the north and for some time with the girl's parents in the west in Bombay.


So, what was behind the two shirts Ram asked Raj. Well, offensive tshirt 1 said "CS graduates are very ... boring" and offensive tshort 2 said "Am I cute? ... No Shit!"

Ram smiled and said, "Thanks for letting me know. If I was less busy when we were in the Institute, I would have understood how all this worked". Atleast, I will be on the watch out for friends of mine Read the rest of this entry >>

Unitary graph scheduling problem

Approaches:

All pair shortest paths
max-flow?
--

LP formulations of the computability/scheduling problem

Motivation: Given that we have a matrix of size (n+d)*m which contains the components {0,+1,-1}. There are many ways in which we can formulate a linear program with this matrix somehow acting as constraints. Let us observe the different ways we can do so, for a close enough look at the linear programs may yield insights into the unitary graph scheduling problem.

Standard/state-of-the-art way (as in Darte-Vivien): Associate the variables of the LP problem to the columns of the matrix. We have m variables in the LP program. This can be thought of as (i) associating variables to edges of the hypergraph and also, (ii) associating variables to the edge-vertices of the bipartite graph. If a hyperedge has a zero component, we throw it away before sending it to next level.

Dual problem with n variables: What if we associate weights with vertices of the RDG? then we somehow can obtain the depth that node is disassociated with the rest of the graph. This is the matrix that Darte-Vivien use for scheduling at every level.

Dual problem with (n+d) variables: This has not been previously expored. We associate a variable to each of the (n+d) "vertices" of the bipartite graph.

many constraints:What if we associate weights with edges of the bipartite graph? There will be (n+d)*m elements we have to find.

Using the decomposition tree: Assume that the decomposition tree is given to us. How do you find the schedule component for each of the variables at that depth?

--
Bipartite matching Tarjan's algorithm and Hopcroft-Karp's matching algorithm, and Vazirani's algorithm. What is the connection between Bipartite matching and SURE scheduling?

Hall's theorem and its variants from Khuller's notes. Hypergraph basics from Berge's book.

--
What does a zero weight cycle in th RDG meain the hypergraph. What does it mean in the bipartite graph?

How does the EDG of the hypergraph look like?

How does the EDG of the hypergraph look like? What are the vertices, what are the edges?

A zero weight cycle in the EDG corresponds to the computability problem of the usual SURE. When does a "node" in the hypergraph-EDG have to wait for infinite time before its computation starts?

(taking a cue from KMW in their statement/proof of colrollary1) What if we think the n vertices also as the dimensions? so the computability problem is a URE in n+d dimensions. How do you label the 'n' to be similar to the 't'? You may want to use this in proving some properties of the URE. The example are lower/upper bound for the schedule. lower/upper bound for the memory allocation.

When does the hyper-EDG have a node which has an infinite length path ending in it?

If loops in the EDG are hindering you, forget them for a moment.

It is clear that the usual EDG has the linearity implicitly embedded in the structure of the polyhedron. We are somehow destroying it by using the hypergraph representation.

Possible correspondence: All this is ok. but, given a hyper-RDG, How do you reconstruct the EDG? vertices of the hyper-RDG: For each of the vertices of the hyper-RDG, we have a corresponding vertex at every point in F_n. Edges of the hyper-RDGIn the hRDG, if vertices v1 and v2 participate in an edge h_e -- which will actually be used a function, returning a set of vertices of the hypergraph, the V (meaning v_h and v_t), exactly 2 and the W set, represented by w_i --, then there is a edge between vertices (v_h,z) and (v_t,z-z') with z' being a d dimensional vector and z'_i = 1 if d_i belongs to the set W and z'_i = 0, if d_i does not belong to W.

What does incomputability mean in the hRDG? A vertex v_i of the hRDG is computable if there exists a path of infinite length ending in it.
--

How hard is the Software-pipelining problem (If it is NPO, what is the best approximation algorithm possible)?

How hard is the SURE scheduling problem? Can we do faster for a special case?

How hard is the SARE scheduling problem?
--
Is it possible to obtain a Theta((n+d)*m) multi-dimensional scheduling algorithm (or even faster)?
--
The algorithm for maximum matching also -- like max flow problem -- seems to use the idea of augmenting pathsRead this link
--
Ideas for Polynomial schedules (possibly better than linear schedules and are a kind of free schedules)
If we divide the vertices of the hypergraph into actual-vertices and dependence-vertices, it is clear that, if a AV does not have an path of length 1 from one DV, then that AV can be computed independent of that dependence component. OTOH, if a AV does not have a path of length 1 to one DV, then the AV can be computed....

Also, if an AV is is not connected to a DV, then that component of AV can be computed independent of that DV. If so, that vertex has a schedule that is a polynomial of better degree that rest of the vertices. If no vertices exist which satisfy these conditions, then the best polynomial schedule has degree of d. Read the rest of this entry >>

Berge: Theory of Graphs

It seems that the concept of incidence matrix was started by Kirchoff.

Representation of a graph: A graph can be represented as a pair (X,Gamma) or (X,U). Gamma is a function from X -> X. This encodes multi-graphs and infinite graphs (if we allow Gamma to be a multi-function). U is a subset of the possible arc sets. If U is a symmetric set, then the graph is undirected.

Chapter 3

Core concept: bounded is different from finite. Finite is different from infinite.

If a set has bounded number of elements, its cardinality is finite and not infinite.
If a set has unbounded number of elements, its cardinality could be finite, or infinite.
If a set has finite-unbounded number of elements
A good example is the 1-d graph which starts at origin and extends unboundedly towards right. Each node on the graph has edges to its immediate left neighbour and all the nodes to its left. For such a graph, the outdegree of any given vertex is unbounded. Still it is finite!!!

Also, a set could have unbounded number of elements and still be finite.

Finite Graphs: A graph is called finite if |X| is finite.

[If there exists a function that maps a vertex of the graph to a natural number, then the graph is not finite. Further, it is an infinite graph. Also, there seems to be many types of infinite graphs. However, Berge gives talks about certain types of infinite graphs meaning ones that satisfy some conditions, esp. the early theorems so that the results of finite graphs can be extended to those types of infinite graphs.]

Gamma-finite: A graph is Gamma-finite, if Gamma(x) < inf for all x in X. (This means that every vertex has finite number of edges out it.)

Gamma^-1-finite: A similar definition about Gamma^-1 rather than Gamma (Gamma^-1 is the inverse of the function Gamma.)

A graph is called locally finite if it is both Gamma-finite and Gamma^-1-finite. Also, a finite graph is locally finite.

Gamma-bounded: A graph is said to be Gamma-bounded if there exists a m such that Gamma(x)<=m for all x in X.

Progresssively finite: A vertex v is progressively finite if no paths of inf length start at v. A graph is progressively finite if is is progressively finite at each of its vertices. [see a note below about progressively finite and having no circuits.]

Progressively bounded: A graph is progressively bounded at vertex v if a number m exists such that the length of all paths starting from v is less than or equal to m. A graph is progressively bounded if it is progressively bounded at each of its points.

The relations regressively finite and regressively bounded are similar to the definitions of progressively finite and progressively bounded. The later deal with the graph (X,Gamma), while the former deal with the graph (X,Gamma^-1).

Relevant examples

RDG: An RDG is a finite graph. So it is Gamma-finite and Gamma^-1-finite. It is also Gamma-bounded and Gamma^-1 bounded. It is usually has cycles, as we deal with a strongly connected component of the RDG. So, it is not progressively bounded. Neither is it progressively finite. It is also not usually regressively bounded and not regressively finite.

EDG of a RDG defined across a finite domain: Such a graph is a finite graph. It is also Gamma-finite and also Gamma^-1 finite. It is also Gamma-bounded and Gamma^-1-bounded. It is progressively finite, if its associated SURE is computable and there exists a schedule. It is progressively bounded if the SURE has a bounded schedule. What about regressively bounded and regressively finite???

[actually the graph theoretic definitions preceed the definitions of computability and schedules. Here we will allow circular definitions.]

EDG of a RDG defined across the entire positive orthant: Such an EDG is an infinite graph. It is Gamma-finite and also Gamma^-1 finite. It is also Gamma-bounded and Gamma^-1 bounded. It is not progressively finite and so is not progressively bounded. It is also not regressively finite and so is not regressively bounded.

EDG of a RDG of a SARE defined over a finite domain: Such a graph is a finite graph. It is Gamma-finite, Gamma-bounded and so Gamma^-1-finite and Gamma^-1-bounded. It is progressively bounded, and progressively finite. It is regressively bounded and regressively finite.

EDG of a RDG of a SARE defined across the entire positive orthant: Such a graph is not finite. It is not Gamma-bounded. Neither is it Gamma^-1-bounded. It is Gamma-finite and Gamma^-1-finite.

I donot know about the computability conditions of either of the types of SAREs. So, no statements about the progressively.* and regressively.* for now.

Theorems

Theorem 1: If a graph is finite, the properties progressively finite, progressively bounded and 'without circuits' are equivalent.

[Note the implication of 'without circuits': If a graph is finite and it is progressively finite, it cannot have any circuits, as that will lead to having infinite path lengths beginning at any of the vertices participating in the circuit. A similar statement can be said about the progressively boundedness of a finite graph.]

Proof of therorem 1: Direct from applying the definitions to a finite graph.

[This proof is kind of easy, because, for a finite graphs |X| < inf. Also, if it does not have any circuits, there exists a bound on the maximum length of a path from each vertex. So, the graph is progressively bounded and is trivially progressively finite. As Berge himself says, infinite graphs are more interesting.]

Questions on the wording of theorem 1: Theorem 1 talks about the equivalence of 'progressively finite' and 'without circuits' for finite graphs. When are the properties not equivalent for infinite graphs?

[which of the 'progressively finite', 'progressively bounded' and 'without circuits' implies the other? It seems that 'progressively finite' combined with 'the graph is finite' is enough. The other two properties seem a little too strong.]

Answer: My current answer is the following: It does not seem that we can give a statement about all paths of an infinte graphs. Why not?
Answer 2: Is one of the conditions 'progressively finite' necessary for the other? and that the other is a sufficient condtion? Is it that the necessary condition and sufficient conditon are satisfied by finite graphs and only one of them is satisfied by infinite graphs?

Meaning of infinite path: What does an infinite path mean? When is a path infinite and when is it finite? Suppose we had just three vertices and a circuit along them, how many paths are there? Suppose we have an infinte number of vertices and the graph does not have loops and circuits. Does the graph have any infinite paths?? NO????? Are we getting confused between an infinite path [meaning a path of infinite length] and infinite number of paths?

Infinite sets: Here are two defs of infinite sets. 1 , 2.

A circuit induces an infinte number of paths on each of the vertices participating in it. Each of the infinite paths is of finite length. An infinte graph (for example the 1-d graph) has infinite number of paths, each of finite length. THEN WHAT IS AN INFINITE PATH? A path whose length is neither bounded by any integer nor there exists a finite number which can specity its length. What is such an example?

Theorem 2: If a graph is progressively finite and Gamma-finite, we have Gamma-hat(x) < inf for all x in X.

The theorem is kind of disturbing. This is because, it states that even in a graph with infinite number of nodes, it gives a statement about the cardinality of the set Gamma^hat. It says that the cardinality is a number, which is possibly unbounded. However, it is a finite number. See the definition of Gamma^hat.

Proof of theorem 2: Suppose the graph is progressively finite and Gamma-finite and that we had a vertex such that Gamma-hat(x)=inf. As the graph is Gamma-finite, x should be adjacent to a vertex x1 such that Gamma-hat(x1)=inf. by similar reasoning, x1 must be adjacent to x2 such that Gamma-hat(x2)=inf. etc... The path [x,x1,x2...] is therefore of inf length. Which contradicts that the graph is progressively finite.

Proof for necessity of theorem 1's premise: The method followed is proof by contradiction. The technique is the following: The theorem statement is of the form: A => B => C. With A being 'graph is Gamma-finite', B being 'graph is progressively finite', C being 'for all x in X, |Gamma^hat(x)| < inf '. B=>C is equivalent to NOT(B) OR C. We assume its contradiction is true; i.e., B AND NOT(C) is true and get a contradiction with A. proof method is: B and NOT(C) means, 'the graph is progressively finite' and 'there exists a vertex x (in X) such that |Gamma^hat(x)| = inf'. To get: contradiction with 'Gamma-finiteness of any vertex of the graph'.

let v be the vertex such that |Gamma^hat(x)| = inf. Let k be the number of paths out of v [objective: k is infinite] The graph is progressively finite meaning 'there exist no paths of infinite length' => all paths out of v are of finite length => There exists a path of maximum length (this is because, in a set of numbers of which infinity is not a member, we can always select an maximum). Then k*length_of_the_max_length_path is the upper bound on the number of vertices reachable by v. By hypothesis, this number is infinite.

Corollary 1: A Gamma-finite which is progressively finite at a vertex x0 is also progressively bounded at x0.

[The real punch line to this benign looking proof is applying the absolutely harmless looking theorem 1 to the subgraph induced by Gamma-hat(x) which happens to be finite.]

Proof of Corollary 1: The subgraph determined by the set Gamma^hat(x) is finite! So, applying the theorem1 to this subgraph, the terms 'progressively finite', 'progressively bounded' and 'without circuits' are equivalent.

[note the equivalence of 'without circuits' and 'cardinality of Gamma^hat(x)' as implied by the statement of this theorem.]

Fillable Holes in the proof of Corollary 1: from G to G' and back again. How can we make a statement about the graph G' when all we are talking about is about the subgraph induced by Gamma^hat(x0). Also, when and how are theorem 2, theorem 1 used? At what particular locations? How is the result for G' extensikble to G? remember, we are talking about two graphs here, G and G'. Also about two theorems 1 and 2. The statement of corollary 1, from the outside is more general, but needs to be taken care of.

Proof by contradiction: If Read the rest of this entry >>

Index Set Splitting of PUREs

(We use the notation of Saouter-Quinton-1203)
PURE: a Parametrized Uniform Recurrence Equation.
Index set splitting is a transformation that finds out if splitting a system of equations into individual sub-components can result in a set of SUREs. The scheduling of which can result in a better schedule.

What can be done better for PUNREs (Parametrized Unitarized Recurrence Equations).

Simple example for index set splitting:
Let the domain be 1 <= i,j <= N (the positive quadrant)

i <= j, X[i,j] = f(X[i,j-1])
i > j, X[I,J] = f(X[i-1,j])

The system can be broken down into two sub-domains
i <= j and i > j. Each of the subdomains have 1-d schedules. Read the rest of this entry >>