BR Maths Corner-1

SaiK · Post by **SaiK** » 25 May 2013 02:28

excellent guru k, 'll download the djvu and read them at home. thx again.

and thanks to guru m for the link above.

kasthuri · Post by **kasthuri** » 25 May 2013 02:29

matrimc wrote:AS ji, could you please expand on the theme of numb3ers show? I haven't seen it. That said, for applied math, Strang's book by the same name has a quite wide coverage - from Linear Algebra/numerical methods perspective. The book was out of print but looks like it is back in print at Amazon

Introduction to Applied Mathematics [Hardcover]
Gilbert Strang (Author)

At $150+ it is a tad expensive. I bought it long time back used. If you are buying used, try to get the one after 1986 which will contain Karmarkar's Interior Point Algorithm.

Oh that reminds me, at one point I thought Strang's online lectures were really good. Here are free lectures from MIT open courses.

http://ocw.mit.edu/courses/mathematics/ ... -lectures/

Linear algebra is absolutely required for any applied mathematician/theoretical physicist. The applications of LA ranges from cryptography to quantum mechanics. I would dare say no other math is as useful as linear algebra. Horn and Johnson's Matrix Analysis is another good book to have around.

kasthuri · Post by **kasthuri** » 25 May 2013 02:39

abhishek_sharma wrote:al kasthuri miyan -- also bliss to suggest good books on applied math-- for example, the books that discuss methods used in Numb3rs TV show. Dhanyavaad onlee.

Also, please enlighten me on Numb3rs show. I have no idea on what they air...

abhishek_sharma · Post by **abhishek_sharma** » 25 May 2013 02:52

Actually they do a lot of hand-waving ...but they claim that they are using mathematical ideas (like wavelet analysis, geographic profiling) for solving crime-related problems.

I had a few courses in linear algebra but the course did not discuss Comp-Sci related applications...

http://en.wikipedia.org/wiki/List_of_Nu ... eason_1%29

SaiK · Post by **SaiK** » 25 May 2013 02:57

So, related questions..

http://en.wikipedia.org/wiki/Adjacency_matrix
can you or guru m/ any one gyan me some intro.. how do I map the Aij matrix to which node of the labeled graph vertex? meaning which node are they talking on the first example?

Vayutuvan · Post by **Vayutuvan** » 25 May 2013 03:01

Yes to Horn and Johnson. Instead of jumping straight into that book start with "Linear Algebra Done Right" which is quite good in spite of the snarky title. All theorems are proved with no recourse to determinants purely algebraically. All one needs is mathematical induction and maturity (mathematical - emotional not all that much). Then onto Horn and Johnson for theory of LA, Golub and von Loan for computations and algorithms (Bible for textbook type algorithms including good discussion on BLAS Levels 1, 2 and 3 algorithms) supplemented by Lapack and BLAS and possibly Matlab for experimentation, Saad for iterative methods, Ortega for parallelization, Algebraic Eigenvalue Problem by Wilkinson (perturbation, condition numbers, error analysis and all the fun numerical stuff that can go wrong when doing large scale computations) and one is set.

If one is interested in Signal Processing (which is an important and large application area), then look into Circulant Matrices and the generalizations called Low Shift Rank Matrices. There is a book by Kailath who is the leading researcher in the area.

If your interest is to solve large Linear Systems (sparse ones usually) then look at Daniel Speilman's papers and support theory. That should cover one kind preconditioning. The other is multigrid type preconditioned iterative methods.

Probably should take about 2 years.

kasthuri · Post by **kasthuri** » 25 May 2013 03:10

abhishek_sharma wrote:Actually they do a lot of hand-waving ...but they claim that they are using mathematical ideas (like wavelet analysis, geographic profiling) for solving crime-related problems.

I had a few courses in linear algebra but the course did not discuss Comp-Sci related applications...

http://en.wikipedia.org/wiki/List_of_Nu ... eason_1%29

You mean they did not cover numerical linear algebra? Linear algebra finds a natural position in computing. Matrices are nothing but linear transformations between vector spaces. The entires in a matrix are the co-efficients of a basis that map to another basis. In fact, the space of all matrices of dimension 'n' is isomorphic to the space of linear transformations that map any two vector spaces of dimension 'n'. So, whenever we are dealing matrices, be it image processing or finite element methods, we need LA. The best application of LA in Comp.Sci is numerical methods and there are plenty of good books. Let me know what particular aspect of applied math that you are interested in.

SaiK · Post by **SaiK** » 25 May 2013 03:14

~~I think I am slowly getting it.. but only if the node numbered for the right i,j. am i on the right track?~~

i got it.

kasthuri · Post by **kasthuri** » 25 May 2013 03:16

matrimc wrote:Yes to Horn and Johnson. Instead of jumping straight into that book start with "Linear Algebra Done Right" which is quite good in spite of the snarky title. All theorems are proved with no recourse to determinants purely algebraically. All one needs is mathematical induction and maturity (mathematical - emotional not all that much). Then onto Horn and Johnson for theory of LA, Golub and von Loan for computations and algorithms (Bible for textbook type algorithms including good discussion on BLAS Levels 1, 2 and 3 algorithms) supplemented by Lapack and BLAS and possibly Matlab for experimentation, Saad for iterative methods, Ortega for parallelization, Algebraic Eigenvalue Problem by Wilkinson (perturbation, condition numbers, error analysis and all the fun numerical stuff that can go wrong when doing large scale computations) and one is set.

If one is interested in Signal Processing (which is an important and large application area), then look into Circulant Matrices and the generalizations called Low Shift Rank Matrices. There is a book by Kailath who is the leading researcher in the area.

If your interest is to solve large Linear Systems (sparse ones usually) then look at Daniel Speilman's papers and support theory. That should cover one kind preconditioning. The other is multigrid type preconditioned iterative methods.

Probably should take about 2 years.

Golub and von Loan is a great book. It is the book that helped me get the insights of FFT's and convolutions in terms of Toeplitz and circulant matrices. I had the opportunity to meet Golub when I was at grad school. I guess he passed away. My advisor was a pre-conditioning guy, although I did not get into that topic for my research.

abhishek_sharma · Post by **abhishek_sharma** » 25 May 2013 03:20

Yes, I know that linear algebra is very important for CS. But I took that course in the Math dept, and they discussed the properties of rings and fields for a while....it was just theorems and lemmas ....

There was that red-colored book on linear algebra...what is its name? I will try to find it.

SaiK · Post by **SaiK** » 25 May 2013 03:24

Is this a good book?
http://www.amazon.com/Graph-Algorithms- ... 0521736536

Vayutuvan · Post by **Vayutuvan** » 25 May 2013 03:54

Saik and AS,

I think going through Cormen, Lieserson, Rivest, and Stein would be quite fruitful, especially computational LA and matrix algorithms. Adjacency Matrices are given in that book. I have an old copy (before Stein came on board) so can't say which chapters. But the first two or three chapters are a must for algorithmic analysis purposes - asymptotic notation of big Oh, big Omega, little omega, little oh, and Theta, master theorem for solving recurrences. Then you can jump to Matrix algorithms which explains Strassen's matrix multiplication, equivalence between Matrix Multiplication and Inversion, and FFTs (for Signal Processing).

AS, the book for matrix algorithms is Golub and von Loan supplemented by Numerical Algorithms in C.

Vayutuvan · Post by **Vayutuvan** » 25 May 2013 04:02

SaiK wrote:Is this a good book?
http://www.amazon.com/Graph-Algorithms- ... 0521736536

Shimon Even is supposed to be very good. I haven't read it other than some selected parts. Cormen should cover a lot. Supplement with Reingold, Nievergelt and Deo (it is a little dated but good number of good problems).

kasthuri · Post by **kasthuri** » 25 May 2013 05:26

abhishek_sharma wrote:Yes, I know that linear algebra is very important for CS. But I took that course in the Math dept, and they discussed the properties of rings and fields for a while....it was just theorems and lemmas ....

There was that red-colored book on linear algebra...what is its name? I will try to find it.

Yes, I know what you are talking about. Why don't these mathematicians just don't get anything outside fields and lemmas... pure

On the other side of this fence, few days back I was chatting with Stephen Smale and he was claiming himself a biologist! It was really funny because his lecture was almost mathematical in the computational biology department where nobody from our side (I belong to the wet labs where we do "real" biology like knock-down experiments) considers even cbio folks remotely biologists. When in-slico is just not in-vitro and totally different from in-vivo, I am really not sure what made Smale to think himself as a biologist. But at least he is reaching out...

abhishek_sharma · Post by **abhishek_sharma** » 25 May 2013 06:56

matrimc: Thanks.

kasthuri: To be fair, it was a course offered by Math department, and mathematicians are not obliged to teach Comp Sci related stuff. This guy was at IIT Kharagpur at that time, and taught the course. He is a really nice guy (although the course was pretty boring).

Vayutuvan · Post by **Vayutuvan** » 25 May 2013 07:32

I prefer sage that can be obtained from www.sagemath.org for experimentation with Discrete Math, Graphs, Combinatorics, Logic, Linear Algebra, and {Number Theory and Crypotgraphy}. Sage is quite strong in the last two. Combinatorics probably is a little weak and numerical LA definitely weaker than Matlab. Graph theory is probably pretty good (the competitor is some kind of graph algorithms from Knuth's lab). For computational geometry, CGAL is very good. Sage can integrate several Optimization packages including Gurobi. All FLOSS, so no cost and all the glue is in Python.

kasthuri · Post by **kasthuri** » 25 May 2013 07:53

@abhishek_sharma: I don't have problems about any particular mathematician - after all we all are limited by the knowledge we posses. And we need experts in any particular field and its subfields - otherwise the field wouldn't grow. I grew up with lots of good and excellent mathematicians. I am talking about collective efforts. Most often, math departments stay aloof, esply. pure mathematicians with almost zero collaboration with CS and other depts. including physics. I would blame it on the system that wants only heros and become torch bearers of their research areas. As a result, we are interested in solving our own little problems. This is not just confined to math department alone, but I see a lot in the math community, especially pure mathematicians. Greater ideas emerge when we try solve pressing problem of our times and that happens when we are bold enough to cross boundaries. Einstein went ahead to understand non-Euclidean geometry, a field that was outside the scope of physics at that time. Time was already ripe for relativity with Minkowski's and Poincare's contribution and Einstein made that leap. And he was a clerk at patent office.

kasthuri · Post by **kasthuri** » 25 May 2013 08:07

matrimc wrote:I prefer sage that can be obtained from http://www.sagemath.org for experimentation with Discrete Math, Graphs, Combinatorics, Logic, Linear Algebra, and {Number Theory and Crypotgraphy}. Sage is quite strong in the last two. Combinatorics probably is a little weak and numerical LA definitely weaker than Matlab. Graph theory is probably pretty good (the competitor is some kind of graph algorithms from Knuth's lab). For computational geometry, CGAL is very good. Sage can integrate several Optimization packages including Gurobi. All FLOSS, so no cost and all the glue is in Python.

So matrimc, what are you? A numerical analyst, theoretical cs person, all-round algorithm developer, graph theorist, computational geometer, programmer...just curious, that's all.

Vayutuvan · Post by **Vayutuvan** » 25 May 2013 09:21

>> A numerical~~analyst~~, theoretical cs person, ~~all-round~~ Linear Algebraic algorithm developer, graph theory as it relates to sparse/very sparse/extremely sparse Linear Equation Solves, ~~computational geometer~~, mainly programmer

with previous interest in Interior point methods for Network flows, Matching, MILP with small number of Integer variables, Linear and Convex Programming, and applications.

Also, did a couple of courses in AI (with Maurice Karnaugh), wanted to do Computer Vision but got turned off due to subject matter and lack of Theoretical CS background just about when I got to my Ph.D. school (different from where I had Prof. Karnaugh). Had some ideas in scheduling for distributed systems, would have got a doctorate in a couple of years, but felt it was not for me. So changed over to Theoretical CS with a very famous *** Algorithms professor who was an ** (which was my undergrad) <snip> He is a true rennaisance man and would work with students side by side. I took a little longer to finish my pachhadi because of all these changes of mind and areas but was a very enriching experience.

abhishek_sharma · Post by **abhishek_sharma** » 25 May 2013 09:30

^^ sahi hai, looks impressive. I am an AI person. Hope to learn applied Math and economics-related stuff in this lifetime.

Vayutuvan · Post by **Vayutuvan** » 25 May 2013 10:00

oh, forgot to mention. Had a Bio-Physics roommate who as working in protein tertiary structure prediction and a couple more MD/PhD friends so used to attend some seminars in Biophysics department and shoot breeze with them late into the night. Also several EE batch mates so lots of interdisciplinary interaction.

kasthuri · Post by **kasthuri** » 25 May 2013 18:10

^^^

Very interesting. I am sure you will have a lot to do after you retire. That is how I think of myself - could not possibly get bored with so many stuffs to get into...

Your academic profile closely matches mine, but I got a very hands off advisor.

Of late my interest in logic is increasing, especially on computability logic. I guess there are not many good books out there for meta-math and other logics. I don't want basic logic books, which I can find. I need little bit advanced. Do you have any recommendations?

Vayutuvan · Post by **Vayutuvan** » 25 May 2013 21:22

Kasthuri , could you please edit the quote above so that my friends' identity is protected? I edited my original posts so that people cannot play 20 questions. Thanks.

kasthuri · Post by **kasthuri** » 25 May 2013 23:46

matrimc wrote:Kasthuri , could you please edit the quote above so that my friends' identity is protected? I edited my original posts so that people cannot play 20 questions. Thanks.

Done deal.

Vayutuvan · Post by **Vayutuvan** » 26 May 2013 01:14

Appreciate it.

SaiK · Post by **SaiK** » 27 May 2013 02:21

kasthuri wrote: So matrimc, what are you?.

I think you get that info from his id itself.
guru of mat-lab, real-time intelligence & master of computations.

sorry, just tried my best to create a definitions for his id. well, at least that is the feeling i have. i am trying to bump up as many gurus as possible in my life.. that is my current mission.

pardon me for a small OT/.
====

http://en.wikipedia.org/wiki/Laplacian_matrix
Can some gurus give some applied gyan on where and how we would use this laplacian matrix (practical purpose - may not be a realistic example)? tia

kasthuri · Post by **kasthuri** » 27 May 2013 08:21

SaiK wrote:i am trying to bump up as many gurus as possible in my life.. that is my current mission.

Hope you don't bump into Nithy types

SaiK wrote: http://en.wikipedia.org/wiki/Laplacian_matrix
Can some gurus give some applied gyan on where and how we would use this laplacian matrix (practical purpose - may not be a realistic example)? tia

Well, as I mentioned few discussions earlier, a matrix is nothing but a discrete version of a linear transformation. If the matrix is square it is called a linear operator (a transformation that maps the space onto itself). Now, you can see a Laplacian matrix is nothing but a discrete version of continuous Laplace operator. And as for as the application of the Laplace operator - there are plenty, including heat equation, diffusion equation etc. etc. as all of these are formulated using Laplace. In any of these application, we need to discretize the operator to solve the differential equation and hence end up with a Laplacian matrix which can then be used to solve a linear system using numerical methods.

One of the cool application of a Laplace matrix is in image processing when we need to identify an edge in the image. As you may know an edge is a sudden change in the gradient. So, one can take the first derivative (of course, partial derivatives) and see where there is a big spike. However, this will be a problem because we do not know the start and the end of this spike. However, from calculus we know at the places of maxima/spikes, the derivative is zero. Thus, if we take the derivative of the gradient, it will be zero at the spikes or precisely where there are edges. Thus, we can accurately detect edges by taking the derivative of the gradient. But the derivative of a gradient is simply the Laplacian. Thus, a Laplacian matrix would help us in identifying the edges of an image to a reasonable accuracy.

kasthuri · Post by **kasthuri** » 27 May 2013 08:49

My SHQ (who is a graph theorist) tells me that spectral graph theory and especially Laplacian matrix of a graph has found some attention in detecting communities in a network. I traced the paper she was referring and here it is:

Detecting community structure in networks

SaiK · Post by **SaiK** » 27 May 2013 21:43

who is Nithy type/class/object?
--
I am impressed with your answers guru kasthuri.. may your kind/types grow at a higher rate. For a math moorkh like me, it is a tremendous oppty. to learn, and hopefully retain and sustain the learning process.

There are lots to learn for me, and more than that lots to keep things in my little cache I have on the head. It is a big challenge for me.

I want to learn methods from here, into applications for automatic control systems. But how far I can get to a clear understanding is a big question. I am trying.

SaiK · Post by **SaiK** » 27 May 2013 23:13

so, on the laplacian, i get the degrees for each node in the graph, and a value (-1) for either the matrix mapping is adjacent to a node or not (0). am i right?

kasthuri · Post by **kasthuri** » 28 May 2013 00:01

SaiK wrote:so, on the laplacian, i get the degrees for each node in the graph, and a value (-1) for either the matrix mapping is adjacent to a node or not (0). am i right?

Absolutely.

kasthuri · Post by **kasthuri** » 28 May 2013 00:13

SaiK wrote:who is Nithy type/class/object?

Nithy means Nithyananda.

SaiK wrote: I am impressed with your answers guru kasthuri.. may your kind/types grow at a higher rate. For a math moorkh like me, it is a tremendous oppty. to learn, and hopefully retain and sustain the learning process.

There are lots to learn for me, and more than that lots to keep things in my little cache I have on the head. It is a big challenge for me.

I want to learn methods from here, into applications for automatic control systems. But how far I can get to a clear understanding is a big question. I am trying.

The word guru makes me nervous especially since I like J. Krishnamurthy. I believe learning is a continuous process since we are all evolving. Lot to learn here as well. I have no clue on how automatic control systems work. I think doing is as much important as learning. Most of the times we tend to emphasize on learning, and then doing. As a result we end up not doing at all. This is the biggest divide between academia and the industry where the former prioritizes learning over doing and the later - doing over learning. A good balance is required. Karma is as important as Gynana. Sorry for sounding philosophical - but that's what I am.

SaiK · Post by **SaiK** » 28 May 2013 03:13

no sorry business here.. to me the word guru definition is all about the laws of transformation of information and knawlidge!. let it come from a kid or an oldie, info is an info is an info. when you present things in a manner learning happens, you have exercised the guru actions correctly.. and that needs to be respected.. and must be paid as sdre dharma is about fee edu. here in a public forum, the payment can come in many ways as well. like paying in kind, at least use the word guru, etc.

Vayutuvan · Post by **Vayutuvan** » 28 May 2013 06:58

SaiK wrote:so, on the laplacian, i get the degrees for each node in the graph, and a value (-1) for either the matrix mapping is adjacent to a node or not (0). am i right?

Now answer this question - what is the rank of a Laplacian?

kasthuri · Post by **kasthuri** » 28 May 2013 08:10

^^^ Excellent question.

SaiK · Post by **SaiK** » 28 May 2013 17:40

nice question.. let me review how to calculate the rank first. 'll revert soon. i need to make some time for this today. thx for the question.

SaiK · Post by **SaiK** » 29 May 2013 02:15

so, the max number of independent rows right (unique, and using elimination steps for row echelon)? kind of reading here and there online from cryptic read to easy ones. And if the degrees match at each nodes, then there can be repetitions .. but that would still be distinct since i,j would be different. I am currently assuming maximum rank would the number of rows itself is my first guess. It should be at least 1 for connected graph, meaning there are two nodes.

but, i will re-review again.. kind of getting there.

Vayutuvan · Post by **Vayutuvan** » 29 May 2013 05:17

You are on the right track.
OK, is it singular?

SaiK · Post by **SaiK** » 30 May 2013 07:21

I was busy today to explore into this.. it looks like a year passed after you asked the question, 'cause my brain just washed all that l learnt a day back so soon. from online sources, the singular matrix is one that its determinant is 0. So, (again assuming), I get by elimination the last row becoming 0, then I am bound to think it is singular.

ref:
http://mathworld.wolfram.com/SingularMatrix.html
http://en.wikipedia.org/wiki/Singular_matrix#singular

still digging for emphatic answers.

Vayutuvan · Post by **Vayutuvan** » 30 May 2013 07:31

saiK, look for a simple answer. If not, Wikipedia is always there.