Solving Root Finding Problem with Sparse Matrix | Krindik

[krindik]

Hi,
While trying to simplify a solution I came up with the following sparse matrix but don't know how to solve it. $$[A(t)][X] = 0$$

$$\left( \begin{array}{ccccc} A_0(t) & 1 & 1 & ... & 1 \\ A_1(t) & 1 & 0 & ... & 0 \\ ... & ... & ... & ... & ... \\ A_{n-1}(t) & 0 & ... & 1 & 0 \\ A_n(t) & 0 & ... & 0 & 1 \\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ ... \\ x_{n-1} \\ x_n \end{array} \right) = 0$$

I need to find solutions for $$t$$ satisfying $$|A(t)| = 0$$

I would really appreciate if you would point me in finding out
1. Whether there is actually an analytic solution for this
2. If not a suitable numerical technique to find solutions

Thanks

Krindik

 

[loveequation]

Note that if you have a solution $\vec x$ to $M\vec x = 0$ then $a \vec x$ is also a solution, where $a$ is a number, i.e., the solution is determined up to a scaling.

Hence you are allowed to set $x_0 = a$. Once you do this you are on your way. You can express the $A_j(t)$ in terms of $x_j$ up to an arbitrary constant $a$.

Hope this helps.

 

[krindik]

Note that if you have a solution $\vec x$ to $M\vec x = 0$ then $a \vec x$ is also a solution, where $a$ is a number, i.e., the solution is determined up to a scaling.

Hence you are allowed to set $x_0 = a$. Once you do this you are on your way. You can express the $A_j(t)$ in terms of $x_j$ up to an arbitrary constant $a$.

Hope this helps.

I'm sorry but I didn't get what u meant exactly. My problem is not actually to solve for $$x$$, rather to solve for $$t$$ such that $$|A(t)|=0$$. Actually I shouldn't have mentioned $$[A(t)][X] = 0$$. I want to find $$t$$ such that $$|A(t)|=0$$ where $$[A(t)]$$ is given as:
$$\left( \begin{array}{ccccc} A_0(t) & 1 & 1 & ... & 1 \\ A_1(t) & 1 & 0 & ... & 0 \\ ... & ... & ... & ... & ... \\ A_{n-1}(t) & 0 & ... & 1 & 0 \\ A_n(t) & 0 & ... & 0 & 1 \\ \end{array} \right) = [A(t)]$$

 

[loveequation]

Confirm that you want the determinant of $A$ equal to zero. If so, I think I know how to solve it.

 

[krindik]

Confirm that you want the determinant of equal to zero

Exactly...

Thanks in advance

 

[loveequation]

For the determinant to be zero you need linear dependence in the matrix. Note that the second, third,...last rows are all linearly independent. To get linear dependence add the second, third,...last rows and compare the result to the first row.

To get linear dependence you want
[tex]
A_0(t) = \sum_{j=1}^n A_j(t).
[/itex]

Does this help?

p.s. You find the same thing if you compute the determinant by expanding in minors. Expanding along the first column for a 4 by 4 case you find
$$det(\sansserif{A}) = A_0 - A_1 - A_2 - A_3,$$
which gives confidence in the original result.

 

[krindik]

Thank you...
Silly me... didnt see it..
Just by doing elementary row operations the ones in first row could be eleminated...

anyway.. I'm back to square one... hoped it could give some easy result eg. $$A_1(t), A_2(t), ... = 0$$ So that
$$A_n(t) = \frac{p_{n2} t^2 + p_{n1} t + p_{n0}}{q_{n2} t^2 + q_{n1} t + q_{n0}}$$ is easy to solve for $$t$$

As I mentioned, have to solve for $$t$$ such that $$A_0(t) - \sum_{j=1}^n A_j(t) = 0$$. So need to find roots of order $$2n$$.
May be I'll have to do numerically or can a symbolic math tool do this?

Thanks

 

[loveequation]

If the denominators of the different $A_j(t)$ have common factors then that helps.
Otherwise just use ZBRENT (a root finder). I assume you want all the solutions. If so, you will have to find all the intervals containing roots yourself before calling ZBRENT.

 

[krindik]

Hi,
I was wondering whether there is any simplification available to find roots for something like
$$\sum_{j=0}^n A_j(t) = 0.$$

where,
$$A_n(t) = \frac{p_{n2} t^2 + p_{n1} t + p_{n0}}{q_{n2} t^2 + q_{n1} t + q_{n0}}$$


Thanks

 

[loveequation]

Hi:

You might want to post your question at the top level so it gets noticed. My guess is no, not for arbitrary coefficients p and q. The only special case which is analytically solvable is where the numerator of each term in the sum has the same root.

If you decide you're going to bite the bullet and program it up using ZBRENT then be sure that the first thing you do in the program is to identify the zeros of each of the denominators. This is where the function blows-up and has an asymptote. You could get a sign change across an asymptote and these should not be mistaken as roots.

Finally, and this makes the job easier, note that the function has flat horizontal asymptotes (i.e., the limits as t tends to infinity). Hence you can choose your
search interval depending based on how close the function is to its horizontal asymptotes.

Good luck. This would take me two hours to complete.

 

[krindik]

Thanks a lot...

Instead of writing my own solver I tried MATLAB root finder. It took more than an hour(but still couldnt) to find roots. Since my requirement is to find roots in terms of some variables in $$p_{n0}, p_{n1},... q_{n0}, ...$$ what I thought of doing was to do a parameter sweep for and find the roots(instead of symbolic root finding). Since that time is not acceptable I went looking for a simplification but in vain...

I googled for ZBRENT but couldn't find any such package/software. Found a single zbrent.c file..

 

[loveequation]

Hi:

Give me an idea. What is the value of "n". I assume you have 6*n p's and q's to vary. What are the ranges of the p's and q's and what is the range of "t".

For certain cases you can be certain there is no root. For example for t > 0 and all the p's and q's strictly positive there is no root.

For a fortran subroutine just google zbrent fortran.

 

[krindik]

Thanks again
n is usually less than 10. p and q are consists of other parameters eg. x, y

it is something like
$$A_n(t) = \frac{(x-a_n) t^2 + (y-b_n) t + b_n^2}{ (y-a_n)^2 t^2 + 2(x-a_n) t + 2b_n}$$

a_n and b_n are numeric constants different for each A_n but the this form is exactly same for all A_n's. i.e only a_n and b_n change.

What I want to find is roots of t as functions of x and y. Since it was possible to do it symbolically, i tried to do a parameter sweep of x and y and find roots of t. That too takes long time for a pair of values for x,y

 

[loveequation]

You want to explore a two-dimensional parameter space. That's easy. But you're going to have to write your own solver with zbrent at its core. The writing of a solver should take about two hours of human work.

Here is a hybrid way to go, i.e., partially symbolic and partially numerical---I suspect both steps can be done in mathematica. If n = 10 then you can put everything over a common denominator and get a single rational polynomial of degree 20. Then the roots will be the roots of the numerator polynomial (provided the denominator doesn't have the same root, which is easily checked). The advantage of this approach over the one above is that you don't have to worry about the vertical asymptotes where the original function blows up.
You're also dealing with a polynomial so that Desartes rule of signs can be used and you know how many roots to expect.

Out of curiosity what is the application?

 

[krindik]

That is so very kind of you... thanks

I don't have mathematica, but believe MATLAB symbolic toolbox can do the first part. (if it fails i'll try to get hold of mathemetica somehow)

I found zbrent.c below. (I've never learned fortran...). If it basically means using this program I'll definitely do it no matter 2 hours or 2weeks it takes :)
http://astronomy.nmsu.edu/cwc/Teaching/ASTR545/HW/zbrent.c"

Actually the application is stability analysis of a system.
Will definitely let u know of the progress.

Thanks again

 

[loveequation]

Good luck.

Here is another think that will help. Suppose you find set of roots for one (x, y). Then if you go to a neighboring (x, y) pair then obviously use the previous roots as a starting guess.
This will go faster this way.