Books and some notes

These are some books

Golumbic's book or Shamir's notes

Schrijver's any of three books: Schrijver1984, Cook... Schrijver, Schrijver2004

Schrijver's lecture notes

Cornuejols's book

An interval graph is perfect. Its interference graph

has consecutive 1's property.

is TUM

--
the reduction to SAT of the simple cycle problem seems to be easy, look at the standard reduction of ILP to SAT.
--
This zero weight cycle problem is something like two flow algorithms running in parallel to each other, checking if the value of one is equal to the other: resulting in a null-weight cycle.
--
more importantly, what can be done when the weights belong to 0, \pm 1??????
gcd?? I meant "any ideas":)
--
Check out linear programming when

dimension is small

when the weights are small: unit distances, in particular

Ckeck out the polynomial time linear programming algorithms (Khachiyan-Karmarkar-Karp) from Schrijver and also from Chong. Also, Meggido's algorithm for fixed dimensions
--
This seems to be a nice pecking order:

linear programming is a black-box-tool that solves all linear problems in polyhedral model, reasonably, with simplex or other ways

a smaller problem is scheduling in polyhedral model: till now uses LP: what next?

max-flow could also use LP, because of known reasons (TUMity, duality property, etc...). We can crank up the blocking flow enough number of times to obtain a near quadratic algorithm.

Read the rest of this entry >>

A simple proof for existence of rational schedules

If total-unimodularity of incidence matrices of digraphs implies max-flow min-cut theorem, why should it not imply integral schedules?
Premise: The incidence matrix of the PRDG is TUM.
To prove: either there exists a null-weight cycle or there exists a multi-dimensional time schedule

let the weight of an edge e_i be given by w(e_i) \in \mathcal(Z)^d
(we will talk about the unitarization case later)


--
to do:

check up darte-vivien for the main statement for schedules

check up the main results about interval graphs: in particular, about unit-interval graphs: and PQ trees in any books

--
notes from schrijver-notes
Interval graphs are TUM
Interval graphs are one more special cases of network matrices (directed graphs are the other special case of network matrices) Read the rest of this entry >>

Network Flow/Network Matrices: some new links

There is a paper by Goldberg and Rao in Beyond the Flow decomposition barrier.
It seems a natural lower bound of O(nm) on the flowproblem does not apply to Sleator-Tarjan as it is a preflow method it uses dynamic trees
I am not very sure about the reasons above. The latter is reasonably clear because of the amrotzed analysis, which treats is surely another way to treat the running time of the algorithm, but the former???
--
According to Spinrad et. al's book on graph classes, Yannakakis has shown a fundamental result about the total unimodularity of network matrices with no odd cycles (does sounds like some kind of bipartiteness?), and more importantly, gave a linear time recognition algorithm for the class.
To get the paper.
--
Have to get this book combinatorial-optimization: packing and covering. This book is supposed to be good.
--
A possible multi-dimensional search algorithm for the unitary PRDG: Create a d-dimensional tree and create a directed graph in each dimension. Now how can we make a cycle in a dimension effect another? Read the rest of this entry >>

Presence of multi-dimensional schedules in a graph theoretic way

Suppose we assume that Bx <> 0
This can be written as two inequalities

Bx >= 1

Bx <= -1

We can search for a vector x that satisfies these constraints using a graph-theoretic fashion.
Hints:

look up the max-flow min-cut proof for TUM.

how did Tarjan solve the problem?

How can this problem be solved in that way?

What does multi-dimensional schedules mean in a graph theoretic way?

Note: Interval graphs are duals of directed graphs. If we transpose the incidence matrix of a directed graph, we obtain a interval graph. Correction: We obtain a interval matrix, not a interval graph. Question: how are interval matrices and interval graphs related?

Things to do
-----------
read the max-flow min-cut from the lecture notes
read the same from Schrijver
read the same from Cook
The theorem essentially uses the fact that if a graph is directed, its incidence matrix is TUM
It can also be checked for TUMity in polynomial time
--

read about network matrices from all three sources
how are network matrices different from directed graphs

some terminology
Weakly connected digraph: if the underlying directed graph is connected
------------------
interval graphs idea
--
read about network matrices from all three sources
interval graphs idea
exercises from lecture notes and cook..
---------------
NOTES from Golumbic:
interval graphs lead to PQ trees => how does that help?
----------------
Interval graphs Vs. interval matrices: What is the difference?
----------------

TUMity is a hereditary property.

Goldberg and Sailesh Rao have an extremely fast algorithm in a graph theoretic way for the max-flow problem. Have a look at it. This is the link.

-----------
A simple proof:
STMT1: TUMity of the directed graph to proof of KMW: This is in the spirit of the max-flow min-cut proof.
statement of KMW: either there exists a null-weight cycle or there exists a (possibly multi-dim-time) schedule
STMT2: Decompose the input PRDG into one whose dependences can lead to a TUM matrix. Use the equivalent of Menger's theorem for getting possibly faster schedules possibly in a better runninhg time Read the rest of this entry >>

TUMity of gray and degray matrices

The matrices which are used to convert from a "real" to gray and back again are total-unimodular. What does this mean in a linear algebraic way? What does this mean in a graph theoretic way?
--
Postscript: The paper by Conforti et. al is a very interesting one.

It classifies a set of SAT problems that can be solved in polynomial time (I noticed this property from the dense book by the second author).

For a JACM paper, it is very short, mainly consisting of one main proof.

What are its implications on a search algorithm? In specific, how does this property help solving SAT using GA or the more general problem of GRAY/BINARY representations?

--
Postscript: Consider a deterministic algorithm. randomize it, and call it a GA. If we define a new space which the GA looks at, it is working like a simplex algorithm by doing a neighbourhood search. Read the rest of this entry >>

Hinduism update

It seems that Buddhism had the following doctrines which were not that prevalent in Hinduism earlier:

significance of ahimsa

construction of huge temples as a place which can be used in a multi-purpose way (including for social events: earlier people prayed only to Indra and others, not particularly in temples)

sponsorship of religion by Kings in some form.

Hinduism followed by

adopting the tenet "Ahimsa Paramo Dharma", by stopping of sacrifices

adopting Buddha as an avatar of Vishnu: someone who can show a way to truth.

building huge temples for Hindu gods (it seems the parctice was not there earlier).

doing a state sponsorship of religion, the main examples being by south indian kings like Raja-Raja-the-great.

The result was there was no Buddhism "left" (if there was such a description), as it had nothing new to offer!! This was the way in which Hinduism assimilated Buddhism.
--
The question of relevance is, suppose Hinduism is threatened by Christianity or Islam in some way, can it save itself in the same way by assimilating it? i.e., 1000 years down the line, do we have

prayers to Christ and Muhammad as prophets.

some kind of acceptance that we are imperfect(other schools in Hinduism can continue to believe the vedantic way of perfectness).

make piligrimage to mecca as a reasonably mandatory one (in hinduism, people can do piligrimages to wherever and as and they want to).

Truly, I am not opposed to any of the above. Though I can think of some ways in which the assimilation could go in a direction that I may not want. What if such a thing happens? What direction could be a dangerous one? Read the rest of this entry >>

Implications of the TUMity on the SAT problem/search algorithms

Things, like searching for a cycle etc., can be done in polynomial time when a graph is TUM. What does this mean for a SAT problem? In general, what does it mean for a search algorithm which tries to solve a SAT problem? Read the rest of this entry >>

The optimal memory tiling problem

Given a (rectangular???)loop nest, with uniform dependences, further, with all dependences in first orthant (with enough skewing), find a time optimal running of the loop nest with the following model
r number of registers with access time of each as t_r (for the registers)
n types of memory references all of access times t_n (for )
further, a memory reference l accesses m[l] number of times its memory
given a schedule, for example, iteration order: i_1 ... i_d
split the iteration space into two types of accesses: i_1 ... i_d and t_1 ... t_d


find the following:
a permutation order for the inter tile and intra tile
given a permutation, give a size of tile in that dimension s_1 ... s_d (each of them could be maximal or of unit size) Read the rest of this entry >>

Dakshinamurty Astakam

The link on Advaita philosophy seems to be good. Has a good explanation of Dakshinamurthy Astakam and its explanation of Advaita. Donot miss the four fundamental Mahavakyas part. I have also added a link to the sidebar.
The following is the common line from the astakam:
Tasmi Shri Gurumurthaye Nama Idam Shri Dakshinamurthaye!
of course we know: Sivaya Gurave namah.
--
Postscript added on 06/23/05: Dakshninamurthy Stotram and Astakam are the same. Written by Shri AdiShankara. have the common 4th line "Tasmay Shri Gurumurhyaye, Nama Idam Shri Dakshninamurthaye". Read the rest of this entry >>

The Unitary graph null weight cycle detection problem

Problem: Given a matrix B of size (n+d)*m, with each element of B from the set {+1,-1,0}, find a column vector x of size m, with each element of x from the set Z+, such that the value of Bx is zero. If no such vector x exists, return and state that no such vector exists. This algorithm should run in logarithmic time in d and polynomial time in n and m.
Some questions and possibly, some answers:

B is not a network matrix. Can a network matrix be constructed from B?

Can we frame a SAT problem from the matrix, given that it is a graph with {\pm 1 ,0}. Better question: can this problem be posed as a coloring/independent set problem? The intuition for this is the ILP formulation of SAT. From the intuitiuon of SAT, the coloring and independent set naturally follow.
--
Postscrip(on 19/6/2005): The unitarization seems to be pretty interesting because

Most unform dependences are in the small number range

We can possibly reason better with matrices which have all elements in a small range {+1,-1,0}

How does this effect memory optimization?

Read the rest of this entry >>

Some questions on KMW and TUM matrices

These are some questions related on KMW and TUM.

The uniformization problem of Darte-Vivien: Take a PRDG with possibly non-uniform dependences and uniformize the graph so that all dependences in the graph are uniform (constant vectors). How can you answer the computability and scheduling problems of the original graph using the transformed graph?

The unitarization problem: Suppose we unitarize the input PRDG so that all components of dependence vectors are from the set {+1,-1,0}? How can you answer the computability/scheduling queries of the original graph using the unitarized graph? How can you use TUM property for this? How is the presence of null weight cycles in the new PRDG related to its TUMness? The size of the unitarized graph, measured in number of nodes/edges, could be exponential in the number of bits used to encode the problem!!! This is because its size dependences on the weights of the original graph, not just the nodes or vertices of the original graph. The proposed unitarization may not be the only way in which we obtain a resultant unitarized-PRDG. We may be able to compress it. Can we just look at the actual nodes of the program, keeping aside the virtual nodes and reason about the computability? Since the depencence distances are in the set {+1,-1,0}, what we have is a kind lattice with edges of unit distance. Even if we forget that its size is large, how do you determine its computability? Let M be the matrix. The computability question is answered very simply by answering the question "Is Mx = 0 for all x?
--
This question is exactly equivalent to asking:"Is M a TUM matrix?" this does not seem right

How do you frame the problem of looking for null weight cycles as searching of the matrix is TUM?

Darte-Vivien's block matrix B has two parts, the top part describing the graph without dependences and the bottom part describing just dependences without directions on the edges. The top part is clearly TUM. How to get a TUM graph from the bottom part?

Or, how to reason about TUMness of B?

The self loops can be handled by adding dummy variables.

What has unschedulability of SURE with mono-dim time scheduling have to do with TUMity?

What has strongly and weakly separating hyperplanes got to do with TUMity?

What does null weight cycle mean for TUM?

What does the dual of the matrix mean in terms of TUM?

What does longest path mean in terms of TUM?
Read the rest of this entry >>

Network matrices and total unimodularity

Reading Schrijver book for TUM. Some notes
Bipartite graphs are TUM.
Directed graphs are TUM.
Max-flow min-cut theorem is a restatement of TUMity
Network matrices (NM) are TUM. NM

are a superset of directed graphs.

are obtained by a tree and the flow it induces on a directed graph.

If we call a tree on a directed graph as T and define the "flow" induced by the tree on the graph by a matrix M, we can characterize the TUMity of M.

There exists two matrices which are not network matrices, but are TUM.

Set of matrices which are TUM = set of NM matrices + those two special matrices.
--
Look up these lecture notes on network matrices. The complete lecture notes is this. The lecture notes give the significant points about TUMity. Also the thesis by Koyntek, which introduces "binet matrices", a generalization of NM. There are some good explanations (esp. figures) in the thesis that are not present in either Schrijver's book or in the book by Cook et. al.
--

M seems to mean a flow. Is that right?

What has simplex algorithm have to do with network matrices?
Read the rest of this entry >>

Khachiyan's ellipsoid method

Tarjan's wonderful book has the following to say (in first chapter) about Khachiyan's ellipsoid method:

1. It is a very clever n-dimensional generalization of binary search
   
2. Khachiyan's method takes approximately the same time for all cases. Simplex algorithm is either very fast, for most cases or very slow for some cases.
   
3. Khachiyan's method seems to use very high precision arithmetic, the cost of which the logarithmic cost measure underestimates
   

Read the rest of this entry >>

LP Duality and Darte's decomposed Software Pipelining

A paper by Darte and others on decomposed SWP finally ends with a LP program. They claim that the constraint matrix of that particular LP program is totally unimodular, and so the feasible solutions to that problem are integral, not just rational. The constraint matrix looks dangerously similar to the constraint matrix of the following problem encountered in a linear programming course (Refer Chong's textbook/lecture notes-17):

Given a LP program in standard form, frame a new LP program that has both the primal and dual variables of the original program as its variables. Or, write a LP program whose feasibilty conditions are exactly of those of the original LP program and also of the dual of the original LP program.
--
Schrijver's book says: if the constraint matrix is total-unimodular, then all the points on the surface of the defined polyhedron are integral. This means that the solution is an integer point, not just a rational one. This also corresponds to the set of problems which are in the set NP \cap co-NP. So, a polynomial time algorithm is possible for those problems. (It can also be said that the same is true for all problems in NP, but it means assuming something, which may be possibly presumptous.:)
--
So, given a usual graph theoretic flow problem, which can be formulated as a LP program, do the following to know if the problem is nice:
"reason about the feasibility of the primal and dual and the constraint matrices of both. If they turn out to be total-unimodular, then the program has integer solutions and the problem is in NP \cap co-NP". Then think hard and write a graph theoretic algorithm to solve the problem.
Note: in such constraint matrices, we usually deal with the incidence matrix, not the adjacency matrix.
Question: We know now know that LP is in P, using any of Khachiyan, Karmarkar, Karp. Then, how much of the above is new? Read the rest of this entry >>

Osborne's translation of Ramana's forty verses

I found an online version of the translation by Arthur Osborne. (I also added the link to the side bar.) It is different from the one by Cohen in the book. Yet to understand either completely. It seems that most of the verses can be reasoned starting from the original truth. Read the rest of this entry >>

Ramana's forty verses on reality

Reading a book on Ramana Maharshi . Also converted Ramana's Forty verses on reality into a mailing list. Some of them are very abstruse, some are very simple. All are very enlightning. A few selections.

1. (Invocation 2) Fear of death is the driving force behind the quest for immortality.
   
2. (1.) Awareness is All - The seer, the seen, the real and apparent.
   
3. (6.) The world is what the mind conceives through the senses.
   
4. (19.) Arguments about destiny and free will are carried on by those who have not realized. Those who have, are free from both.
   
5. (21.) To see God is to be absorbed by God.
   
6. (22.) God shines in the mind. But to know God, the mind has to turn inward.
   

The book also has some translations of Sankara's work by Ramana. More about it later. Read the rest of this entry >>

Systems of Indian Philosophy

Many books on Indian philosophy refer to the six classic indian systems of philosophy. Surendranath Dasgupta's wonderful book (more about it later) gives a nice listing of them.

The systems are divided into the naastika (atheistic) and asthika (theistic) systems, the main difference being whether a system accepts the authority of vedas or not. The naasthica systems are the Buddhism, and Jainism and the Carvaka system.

The asthika systems are
1. Samkhya: attributed to Kapila: most of the earlier works on the subject are said to be lost
2. Yoga: attributed to Patanjali. The original source is Patanjali Yoga Sutras. They are very close to Samkhya (even Dasgupta says that they are so close that we can call them Samkhya-yoga). I quote from vol#1 page 68

"The general metaphysical position of these two systems with regard to soul, nature, cosmology is almost the same, and the difference lies in this that the Yoga system acknowledges a god (Iswara) as distint from Atman and lays much importance on certain mystical practices (commonly called as Yoga practices) for the achievement of liberation, whereas Samkhya denies the existence Iswara and thinks that sincere philosophic thought and culture are sufficient to produce the true conviction of the truth and thereby bring about liberation."

3. Nyaya 4. Vaiseshika: These two are said to be very close to each other.
5. Mimasa (Purva-Mimamsa)
6. Vedanta (also called as Uttara-mimamsa): The Vedanta-Sutras are written by Badarayana (my guess: Vyasa) are mainly in Brahma-Sutras, which are but a summarized statement of the general view of the Upanishads. The most famous commentary is from the great Sankara of the Advaita system.

More about this later. Read the rest of this entry >>

KMW revisited in a graph theoretic way

Problem#1: finding null weight cycles in a dynamic/periodic graph

This problem has many approaches. The interesting ones are the following:

1. Karp-Miller-Winograd's decomposition using LP formulation
2. Kosaraju-Sullivan's decomposition using O(n\log n \times Z) with (n: number of vertices of PRDG and Z the complexity of a LP program)
3. Darte-Vivien using a the idea of decomposition similar to KMW and improving the complexity given by KS to O(n\times Z)

Cohen-Megiddo: seem to give a formulation similar to LP?

Problem#2: The Max-flow problem

1. People first gave an LP formulation.
2. Edmonds-Karp have a graph theoretic algorithm: O(n^2\times m)
3. Tarjan improved it to unbeatable level.

A similar statement can be given to any of the three main problems dealt in Tarjan's book (MST, Path-problem or max-flow)

Question: What can be done so that Problem #1 can be made as Problem#2?

Now, what about Cohen-Megiddo for problem#1? Do they use some kind of LP formulation?
What about Orlin's 1984 paper?
What about Orlin's paper on simplex?
What about Megiddo's simplex paper? Read the rest of this entry >>

Shri Lakshmi Narasimha Karavalamba Stotram and Advaita Vijaya

Lakshmi Narasimha karavalambam Stotam is an amazing stotra written by Shri Adi Sankara in praise of the Nara-smha form of Shri Vishnu. The avatar is said to be one of the few Paripurna avatars of Vishnu. Rama and Krishna are some of the others.

What amazes me about the Stotra is the way it is structured. In every verse, Sankara as the devotee or Jiva, describes the various perils of Samsara, the world or Maya. Each verse ends with the devotee praying to the Lord in Lakshmi-Nrsmha form to save him from the perils of the world. The resulting rhyme is very beautiful. A shloka at the end requests the Swami to save his (the devotee) jiva the way the swami saved Prahlada and other bhaktas like Narada, Ambarisha, Vyasa and Suka.

It is interesting to look at the story behind the Stotra from an Advaita perspective. These seem to be the equivalents.

Prahlada as jiva/soul: He is in union with Brahma, and in Sat-Chit-Ananda at all times and at all places. He feels the presence of non-duality everywhere. He understands the limitation to the powers of maya.

Hiranya-Kasipu as Maya: It first lures the devotee and later threatens with its powers over the world. The maya of course is inferior to the realized-Jiva and cannot destroy, or even torment it. This is because the realized soul sees no difference between pleasure and pain.

Lakshmi-Nrsmha-Swami as the Iswara which saves the soul from the final confrontation. The avatar/form is symbolic of a unity in form as Man-Lion. The destruction of Hiranya-Kasipu happens in the union of dualities like morning/evening, inside/outside, weapon/hands. These opposites however, do not signify a duality but the absence of it. This is because of the boon the Asura asked from Brahma: "the time should neither be morning nor evening, the location should neither be inside nor outside, the utility should neither be weapon nor hands".

The killing of the demon is symbolic to the victory of non-duality over duality. The manifestation of the avatar itself results in the destruction of the stambha, which is immobile and hence signifies ignorance.
--
Postscript: Though he did not mean it, Hiranya-kasipu himself asked for non-duality!!!
--
May Shri Lakshmi Narasimha Swami destroy the ignorance of all of us in the same way!
Lakshmi Narasimha Arpana mastu
Advaita Vijayam Read the rest of this entry >>

Why should Advani fast now? Answer: What Would Gandhi Do?

After his well thought, clever and right move of calling MAJ secular, and resigning as president, what shoud Advani do now?

A clear answer is asking himself, a question which every politician and in fact, every person should ask himself/herself: WWGD (What Would Gandhi Do)?

Advani should fast for some time say, 10 days.

Why? Think about it.

1. It will clear his conscience.

2. It will raise his stature as someone who has recognized his mistakes.

3. Of course, it will raise the standards of the indian politics by a clear notch in the best direction possible.

I further suggest that he fast in Ayodhya near the Ram temple with Ram Bhajan's playing all the time.
Let me know what you think. Read the rest of this entry >>