complexity of KMW aka ZC detection problem

According to Megiddo's 1984 paper, LP is in linear time if the number of constraints is fixed. So, given a (n+d)*m matrix, it is not clear why the algorithm should not be linear if both n and d are fixed or even one of them is fixed. More precisely, if d is fixed, CM-Z give a POLY time algo. What about the case when n is fixed? it is not a POLY time. Is it important? It could be inteersting in cases when n << d.

One difficulty, of course from the fact that the problem has two things (1) A graph defining the dependence directions (2) A set of constraints which define the distances.

Wierd question: Can we make a graph which defines the distances and a set of constraints which define the dependences?
Imagine a network of small nodes (a specific color associated with each nodes of a specific type) with an edge between any two nodes determining the dependence between them.
question: what does it mean when CM-Z say that m = O(n^3) or similar things? Do they mean that the graph is a multi-graph? why not?
--
The main intuition of the Megiddo's 1984 paper on LP is driven by Dantzig's observation: there are many redundant constraints. How can we remove the redundant ones fastly?
--
An oracle gives us the depth of the decomposition tree. Let k be the depth of the decomposition tree. How about making O(log k) queries to the oracle and running a scheduler which could run fast assuming that is the depth of the tree?
--
ala fast mat-mul or gaussian elimination when the depth of the decomposition tree is 1??????
--
Start with an example!!!!!! for 1-d sccheduling and one for unitary problem. The 2 node example of KMW with the self edges removed, has decomposition tree of depth 1. Look up the examples in KMW which are similar to this, and have depth 1. Read the rest of this entry >>

maximal independent subspaces

The main idea of CM-Z is finding maximal independent subspaces (1) without using a LP formulation and (2) in a fast way.
The scheduling matrix is not the same for all the variables if the depth of the decompoisition tree is > 1.
Maybe looking at the following problem would help? How to do fastly, all-pair shortest paths when the weights of the graphs are in the from {-1,0,+1}. maybe looking at Tarjan's result on max-flow under such weights would help?
Problem: You are given a set of variables, with linear constraints between them. You may not have constraints between every pair of variables. However, there are no "unconnected or lonely" variables, as they can be easily removed using a SCC algorithm. How fast can you check if a solution exists for them? or, how fast can you compute a hyperplane that can separate the variables in one shot, if ever you can do it?
--
there are two problems here:

sub-problem1 is to do a fast null cycle detection when the depth of the decomposition tree is known (in particular when it is 1)

subproblem2 is to do the same when the components of the weights are in a known range, in particular, when they are from {-1,0,+1}
--
Look up the definition of P-Complete and NC. Read the rest of this entry >>

happiness: an experience

How many times when we feel happy do we feel a sadness for the time when all this will go away and yearn for an unending stream of happiness? How many times when we feel sad do we long for a Joy/Bliss that never ends? The experience is best described by Ramana Maharshi in his famous forty verses: This is from the translation of Arthur Osborne:

31. For Him who is immersed in the bliss of the Self, arising from the extinction of the ego, what remains to be accomplished? He is not aware of anything (as) other than the Self. Who can apprehend his State?

or the translation by Alan Jacobs

31. Having extinguished the ego, the jnani has no other purpose in life but to remain immersed in the bliss of the Self. What remains to be done by him, who, having extinguished the ego, remains immersed in the bliss of the self? He is aware of nothing but the Self. Who can understand his state?

If Ramana has described it that way, can Shankara be behind? This is how The Master describes happiness in this prasna-uttara-malika:

53. Who lives in happiness?
He who has attained samadhi.

PS: had all these thoughts today. It was amazing. Read the rest of this entry >>

interests, favorite movies, favorite books

I removed the following section from the links.
--
My interests:
Philosophy, Vedanta, Advaita, Theoretical Computer Science, Computational Complexity, Books, Cricket
--
favorite movies:
Gandhi, The Matrix, Lord of the Rings
--
favorite books:
The Upanishads, The Bhagavad Gita, The Ramayana, My Experiments with Truth, Gandhi the man, The sermon on the mount according to Vedanta, On having no head, Zen and the Art of Motorcycle Maintainance, Hamlet, Lord of the Rings, The Art of Computer Programming, A History of Indian Philosophy, Advaita Vedanta: A Philosophical Reconstruction, Sophie's world, Goedel Escher Bach: An Eternal Golden Braid, Advaita Vedanta: An Introduction (Arvind Sharma),
--
A bigger listing of the books, or works of authors I have read, understood and would on any day read again, if I have time. I will add my reviews of all of them some day:

G B Shaw: Saint Joan(amazing), The Devil's Disciple (quite good), Pygmalion and My Fair Lady (who doesn't like these?)
Oscar Wilde: The Complete works, in particular: the four main plays and short stories (brilliant)
O Hentry (complete short stories): possibly the best short story writer
Somerset Maugham: short stories (ok, a little sad: O Henry's OTOH come in all tastes and hues)

Kalidasa: The Main Works: In particular, Raghuvamsham and Kumarasambhavam: awesome!
Richard Bach: Jonathan Livingston Seagull, Illusions
The Alchemist, The Fifth Mlountain,
Harper Lee: To Kill A Mocking Bird: Oh Atticus as Peck!!
James Allen: As a Man Thinketh
Ayn Rand: The Fountain head, Atlas Shrugged, The Anthem
Daniel Quinn: Ishmael, The Story of B, The Man Who Grew Young
Kahlil Gibran: The Prophet
The Little Prince
Herman Hesse: Siddartha
Huxley: Brave New World
George Orwell: 1984, Animal Farm
--
Hosdafter: Goedel, Escher, Bach: An eternal golden braid
G H Hardy: A Mathematician's Apology
Stephen Hawking: Brief History of Time,
Yakov Perelman: Physics for Fun, Mathematics can be Fun
George Gamov: One two Three Infinity
--
Poems by Emily Dickinson,
Poems by Robert Frost
100 best loved poems (a wonderful inexpensive book by dover)
--
Indian Writers
Raja Rao: The Serpent and the Rope (awesome would be understatement), Kanthapura (nice work, He can write simple stories too!), The Cat and the Shakespeare, Meaning of India (his chapters on Gandhi and Nehru are awesome).
R K Narayanan: A tiger for malgudi, The English teacher (near autobiography, very nicely told: one of my early literary experiences), My Days: The official autobiography, Waiting for the Mahatma(runs in a different way from Rajarao's Kanthapura), A tiger for malgudi, Malgudi days, Ramayan (he should stick to what he does best, writing simple stories. BTW, Narayan retells the story of kamba-Ramayana, not valmiki-Ramayana, )
--
Fantasy and adventure
Tolkien: There and Back Again (The Hobbit), LOTR, Silmarillion, The Atlas
J K Rowling, Harry Potter 1,2,3,4,5
--
General
Douglas Adams: H2G2: Trilogy in four parts (the last one was not that great)
--
Simple, no category
The Great Gatsby (ok, ok)
--
Easwaran: Meditation, Gandhi The Man, Mantram Handbook, Dhammapada (one of his best translations) over his Upanishads and Bhagavad Gita
Selections from the Gospel of Sri Ramakrishna
--
Audio Books I liked a lot: The rendering of The Alchemist by Jeremy Irons (nice rendering) and Sophie's world
--
In Bangalore, when I was bored and wanted to know what to reead, I used to refer to this list compiled by Best Web Buys on the best sellers and similar "hot" lists. This is inspite of the fact that I donot like "hot" lists a lot. In Bangalore, I was subscriber of a very good library (One on infantry road: name blue mountain?) and used to buy books from the shop next to Kadambam restaurant(). Why is it that I remember only the landmarks? and why do I remember the restaurant so much:-)? Read the rest of this entry >>

Witness and separating vector computation from CM-Z

One main feature of CM-Z algorithm is the computation of either a witness vector or a separating vector (are they the same? look for the notes below). The other main feature, is the computation of the partition of the graph, using the witness vector or the separating vector.
Defs(from the paper): The existence of a witness vector proves that a (nontrivial) zero-circulation does not exist. On the other hand, if you conclude that there exists no separating vector, then there exists a zero-circulation. Proposition 6.1 seems to suggest that a separating vector is the same as a witness. Is this true only in the case when the depth of the tree == 1????? All this means the following:

zero circulation exists? There exists no witness vector or a separating vector.

no zero-circulation? There is exists a witness and you will be able to find it. and a separating vector.
This is like trying to find a certificate for the problem (zero-cycle detection) or a certificate for the complement problem (scheduling problem). Can the algorithm be made faster if we reverse the direction of the certificate and complement?
--
According to CM-Z, KMW give an algorithm if and when monodimensional scheduling is possible. Of course, they raise the important issue of computability. Roychowdary and Kailath call the 1-dimensional scheduling as hyperplane scheduling. They give a simple LP formulation, (like DV-KMW: I am not sure who preceeds whom), for the case when a 1-dim schedule exists. They also have series of LP formulations, when the depth of the decomposition tree > 1.
--
The main idea of CM-Z is to find a vector v whose null space is maximal independent subspace. CM-Z say that the zero-cycle detection problem is harder than LP. (They reduce the general LP problem to this problem, which is the same thing. They reduce the problem within the POLY time hierarchy. So its ok, it proves some bounds about hardness, donot worry about it.) Since some rows of the constraint matrix have nicer properties. What can be done better? In specific, CM-Z is a general zero-cycle detection algorithm. Can it be specialized for 1-dimensions? i.e., can a maximal independent subspace be found in faster time?
--
Look up the Megiddo's beautiful paper on LP in linear time when dimension is fixed(this is the link), in which he uses a multi-dimensional median search.
What can be done something similar? like, starting from a partially sorted list and increasing the size of the sorted list????
--
added a strang's linear algebra link to the links. A simple question:

if Ax=0 has one solution x=0, then A is non-singular.

if Ax=0 has infinitely many solutions, then A is singular.
What do these two statements mean when A could be TUM??
--
ideas from notes on linear algebra page: matrix multiplication formulation of 1-dimensional scheduling problem. Read the rest of this entry >>

Prabhavananda's book on the Sermon and additional links

Originally, al had asked me to suggest some books on advaita. I thought that his main interests were Christianity and so suggested Shri Prabhavananda's book on the Sermon on the mount as an introduction to Vedanta. Later he replied to me

al hakanson said...
thank you. i started reading the book. but its too dualistic. its god in you, not you are god

This is what i replied

I agree with you. Prabhavananda's book gives a vedantic, not advaitic interpretation of the sermon of the mount. vedanta is the general school of thought from which many schools emerged. Advaita is one of them and is the most prominent. There are other schools of thought, some of which are dualistic, which emerged from vedanta.

To know more about Advaita, I would suggest looking up the wonderful book by Deutsch (which I am also reading) and also the links from the mailing list. Looking forward to your comments.

--
this is Al's link. Read the rest of this entry >>

Notes on Cohen-Megiddo and KMW

Reading Cohen-Megiddo's (CM-Z) paper. Some notes.
The paper does not seem to do a KMW-like decomposition. This is why in the DV-KMW paper, the zero cycle detection of CM-Z result is not used? The algorithm of CM-Z is faster. Also answers the scheduling problem.
--
the papers of KMW, KS, DV-KMW propose a separation of the graph based on some number of calls to LP. KMW propose one per edge, KS propose one ver vertex. DV-KMW propose one call. This results in a sub-graph.
CM-Z call the vector which separates the graph into smaller graphs, a witness. They propose a two step algorithm to compute the witness.

how does the two step algorithm work

what is the meaning of the witness.

what is the difference between the witness of CM-Z and DV-KMW>

--
This paper (......) on improved algorithms for LP with two variables per inequality seems to be interesting.
--
Look up the result on 1-dimensional scheduling in the CM-Z paper Read the rest of this entry >>

Some notes on KMW and unitary graphs

Problems to solve on unitary graphs (directed graphs whose edges are annotated by d-dimensional weights each component of which is from the set {0,+1,-1})

Is the graph computable (does it have a null weight cycle which is not necessarily simple)?

If so, what is the (minimum) dimension of the schedule it allows?

memory optimization1: given a schedule, give a optimal memory allocation for it.

memory optimization2: find the schedule and allocation together, optimally.

--
multi-dim schedules may not be feasible for imperative programs is this right? check up the meaning of multi-dim schedules. look at the example in DV-KMW paper. The example gives a 2-dim schedule for a program in a imperative way.

Assume that the unitary-SURE is computable and that a 1-dim schedule exists. It means that, no null-weight cycle exists and the depth of the decomposition algorithm is 1. So, after one run of the KMW-decomposition algorithm, all the vertices are separated.
having a null-weight cycle is a heriditary property
--
This means that no edge casts a shadow on the another edge => the dot products of any edge weight with any other edge weight is 0???????????????????????
This means that if we (could) enumerate all the self loops to a vertex, the weight of the path is non zero (= condition of no null-weight-cycle). It also means that the weight of two paths that donot touch each other (no common vertex other than itselof) donot combine to zero (can we remove such paths through a initial run of SCC?)
WHAT DOES all the vertices separating in one shot mean?
THINGS TO DO: look closely at the LP programs that they propose. Especially, the variables v and q.
--
q_e is non-zero, v_e is zero on the selected edges. What does that give us?
--
the depth of the decomposition algorithm gives the dimensionality of the schedule. Further, one-dimensional schedules are better than 2-dimensional schedules are better than 3-dimensional schedules are better than ...... Can this be framed as a edge-coloring problem? Can the edges be colored with 1 color? if not use 2 colors. If not use 3 colors.... Or frame the edges as ones which go away in the first shot of the decomposition algorithm, ones that go away in the second shot of the decomposition algorithm....
--
So, begin with a PRDG and see if allows a 1-dimensional schedule => all edges go away after one shot. do the directions of the edges matter?
--
How can all the edges be put in one coloring class? or what does it mean to separate all the vertices of the graph from each other based on just one run of the decomposition algorithm?
--
Things to do: read Cohen-Megiddo's paper and try to apply it to multi-dimension scheduling. Read the rest of this entry >>

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