Printer Friendly

Steady--state analysis of Google--like stochastic matrices with block iterative methods.

1. Introduction. We consider positive stochastic matrices of the form

S = R + uv,

where R [member of] [R.sup.nxn] is a nonnegative and sparse square matrix, possibly reducible with some zero rows, u [member of] [R.sup.nx1] is a nonnegative column vector, and v [member of] [R.sup.1xn] is a nonnegative row vector [30]. The reason behind v representing a row vector will soon become clear. Such stochastic matrices arise in the page ranking algorithm, PageRank [5], of Google (hence, the term Google--like). The objective therein is to compute the steady--state probability distribution row vector [pi] [member of] [R.sup.1xn] of S in

[pi]S = [pi], [pi]e = 1,

where e is the column vector of ones. The first difficulty lies in that although S does not have any zero elements, one must make every effort to avoid fill--in and work in sparse storage since R is a sparse matrix and uv is an outer product. The second difficulty is related to the reducibility of R, since an arbitrary partitioning of a reducible matrix will not yield irreducible diagonal blocks, and hence, care must be exercised when employing block iterative solvers as we shall see. These rule out direct methods such as Gaussian elimination (GE) and iterative methods which require relatively large memory such as preconditioned Krylov subspace methods.

Now, let P [member of] [R.sup.nxn] be the transition probability matrix associated with the hyperlink structure of the web of pages to be ranked and [alpha] [member of] (0,1) be the convex combination parameter used to obtain a positive stochastic matrix S so that it is ergodic and therefore can be analyzed for its steady--state [35]. In the PageRank algorithm,

R = [alpha]P, u = e - Re,

and v is the nonnegative personalization probability distribution row vector satisfying ve = 1 . Note that P may have zero rows corresponding to dangling nodes; i.e., web pages without any outgoing hyperlinks. An equivalent formulation and an extensive discussion on PageRank can be found in [24]. The PageRank algorithm computes [pi] iteratively using the power method. And ranking pages corresponds to sorting the pages (i.e., states of the underlying discrete--time Markov chain, DTMC) according to their steady--state probabilities. The problem is introduced during the Stanford Digital Library Technologies project (now known as The Stanford WebBase Project [38]). Since web matrices are extremely large and always changing, computation lasts long and needs to be repeated.

The rate of convergence of the power method depends on the subdominant eigenvalue of S. This eigenvalue is equal to [alpha] for reducible P and strictly less than [alpha] otherwise [18]. Convergence takes place at the rate by which powers of [alpha] approach zero. Thus, convergence is faster as [alpha] becomes smaller. However, the smaller [alpha] is, the higher the contribution of the second term uv and the lesser the hyperlink structure of the web in R influences page rankings. Slightly different [alpha] values can produce very different PageRank vectors, and as [alpha] approaches one, sensitivity issues begin to arise [33]. Brin and Page, the founders of Google, use [alpha] = 0.85 (in other words, a teleportation probability, (1 - [alpha]), of 0.15), and for tolerance levels measured by residual norms ranging from [10.sup.-3] to [10.sup.-7], they report convergence within 50 to 100 power iterations [5]. We remark that, normally v = [e.sup.T]/n (i.e., the uniform distribution) is used. However, when the web surfer has preferences and is therefore biased, a personalization vector other than the uniform distribution must be used. Hence, ideally the problem needs to be solved multiple times for different personalization vectors.

A number of improvements are made over the power method for the PageRank algorithm. Here, we mention some that are relevant to our work in this paper. The work in [1] suggests using the most recently computed values of the approximate solution in the same iteration as in the Gauss--Seidel (GS) method. This approach, which is classified under sequential updates by the framework in [27], is shown to bring in savings of about one half in the number of iterations with respect to the power method. The power method is also improved in [20], this time using quadratic extrapolation, but the improvement is fairly sensitive to how frequently the extrapolation strategy is invoked. A restarted variant of the Arnoldi algorithm is investigated in [17] for computing PageRank. Although timing results and exact memory requirements are not provided, the results promise considerable computational savings over the power method at the expense of relatively large memory requirements (since a relatively large number of solution vectors of length n need to be stored). A more recent study [16] shows that improvements in number of matrix--vector multiplications (which is essentially the number of power iterations) are possible with inner--outer iterations with modest memory requirements.

Another group of work relates to the way in which the web pages of interest are obtained by crawling. By sorting the pages according to their addresses and then parsing the addresses into separate fields, the authors in [21] have looked into block partitionings of web matrices in which each diagonal block represents the hyperlinks among pages within a domain. Domains in turn can be partitioned into hosts, thus resulting in the view of nested blocks and a method based on iteratively analyzing the diagonal blocks in isolation, aggregating them, and solving the aggreated system. This approach, which is classified under reiterated updates by the framework in [27], is shown to yield savings of about one half in the number of iterations with respect to the power method applied to the original order of pages, although the savings in time do not compare as favorably with respect to the power method applied to the sorted order of pages. An approach based on aggregation is also followed in [6], where a fixed solution is assumed for the diagonal blocks associated with hosts, thereby resulting in a faster but approximative method.

In this paper, we do not assume any knowledge about addresses associated with web pages, take a sparse matrix view, and present the results of numerical experiments with a software tool [10, 11] for the steady--state analysis of Google--like matrices in a sequential setting; i.e., on a computer with a single computational core. The objective is to systematically compare and contrast different sparse iterative solvers. The tool can also be used to analyze irreducible DTMCs as in [34] for their steady--state distribution by setting [alpha] = 1 . There are eight solvers available. These are power (POWER), power with quadratic extrapolation (QPOWER), Jacobi over--relaxation (JOR), successive over--relaxation (SOR), block JOR (BJOR), block SOR (BSOR), iterative aggregation--disaggregation (IAD) with BJOR disaggregation step (IAD_BJOR), and IAD with BSOR disaggregation step (IAD_BSOR). The JOR and SOR solvers become respectively the Jacobi (J) and GS solvers for value 1 of the relaxation parameter. The motivation of the study is to identify those sparse solvers that decrease the iteration counts and solution times with respect to POWER without increasing the memory requirements too much. The contribution of the results to the literature are in the understanding of the type of partitionings to be recommended with block iterative solvers for Google--like stochastic matrices and the benefits obtained by employing them.

It is known that Tarjan's algorithm [36] can be used to symmetrically permute a matrix of order n with a zero--free diagonal to block triangular form in which the diagonal blocks are irreducible [14]. Its time complexity is O(n) + 0([tau]), where [tau] is the number of nonzero off--diagonal elements. In the context of web matrices, this permutation is first noted in [1]. The permutation is later pursued in [31] on parts of two web matrices and some preliminary results have been obtained with an IAD_BJ like method. However, the implementation has not been done in sparse storage and only iteration counts are reported, whereas, timing results are vital for this kind of study. The study in [13] is another one which considers symmetric permutations of web matrices to accelerate convergence of solution methods and is the most relevant one to the work in this paper. Therein, the effect of using breadth first traversal of the nodes of the web graph to generate a permutation of the corresponding matrix to block triangular form is investigated together with sorting the nodes for decreasing/increasing in/out--degrees. Experiments are conducted on one web matrix with one value of a using power, Jacobi, GS, backward GS, and block GS (BGS) methods. The setup times to obtain the permutations used are not reported. Nevertheless, results on the web matrix suggest savings of about a half with BGS in the number of iterations and substantial improvements in solution time with respect to the power method. These two approaches could be classified under reiterated updates by the framework in [27] as well.

In this paper, we use the sparse implementation of Tarjan's algorithm in [37] to obtain a block triangular form and partitionings having triangular diagonal blocks that follow from there. To the best of our knowledge, efficient algorithms that search for the strongly connected components of graphs (which correspond to irreducible diagonal blocks of matrices in block triangular form) use depth first traversal of the nodes as in Tarjan's algorithm. Through a systematic study on multiple benchmark matrices with different values of [alpha], we investigate the merit of various block partitionings. We do not consider any optimization in our code, and treat dangling nodes by considering the hyperlinks to them and not by penalizing [15], recursively eliminating [25], or aggregating [19] them. Hence, the timing results in our work could be improved further. Nevertheless, our results support those in [13], but also show that there are cases which benefit significantly from triangular diagonal blocks, and GS is also competitive.

In the next section, we discuss the solvers. In Section 3, we introduce the partitionings considered with the block iterative solvers. Section 4 is about the benchmark matrices and their properties. Section 5 provides the results of numerical experiments. In Section 6, we conclude.

2. The solvers. Consider the following example web matrix in [24].

Example 2.1. P corresponds to the web graph of 6 pages in Figure 2.1, where probabilities of outgoing links are uniformly distributed and page 2 does not have any outgoing links; i.e., it is a dangling node. P is reducible with the state space partitions {1,3}, {2}, {4, 5,6} forming irreducible subsets of states as in Figure 2.1.

[FIGURE 2.1 OMITTED]

2.1. Power method. Given [[pi].sup.(0)] > 0 and [[pi].sup.(0)]e = 1, the POWER iteration

[[pi].sup.(k+1)] = [[pi].sup.(k)]R + [[pi].sup.(k)]uv for k = 0,1, ...

can be implemented with one vector--matrix multiplication using R and two level--1 operations; i.e., dot--product and saxpy--multiplication of a vector with a scalar and the addition of another vector. Convergence takes place at rate by which [[alpha].sup.k] goes to 0. The smaller [alpha] is, the lesser the effect of the hyperlink structure of the web.

It is reported that by periodically applying quadratic extrapolation for values of [alpha] close to 1, the convergence of POWER can be accelerated [20]. However, the improvement is fairly sensitive to how frequently the extrapolation strategy is invoked, and therefore we do not consider QPOWER further in this paper.

2.2. Block iterative methods. Let

B = [R.sup.T]-I

and E be a permutation matrix so that

A = E(B + [v.sup.T][u.sup.T])[E.sup.T], x = E[[pi].sup.T],

and consider the block splitting A = D - L - U = M - N for Ax = 0 (i.e., E([S.sup.T]-I)[E.sup.T]E[[pi].sup.T] = 0), where

D = diag([A.sub.1,1], [A.sub.2,2], ...,[A.sub.J,J]),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

diag(*) denotes a diagonal matrix with its argument appearing along the diagonal, J, the number of blocks along the diagonal satisfies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] so that n = [[summation].sup.J.sub.j=1] [n.sub.j], [A.sub.j,j] has [nz.sub.j] nonzero elements, and M is nonsingular. We remark that A is a symmetric permutation of [S.sup.T]-I, and that E is neither explicitly generated nor stored but rather obtained using integer permutation vectors as we shall see.

Given [x.sup.(0)] > 0, [e.sup.T][x.sup.(0)] = 1, and the relaxation parameter [omega] [member of] (0, 2), the iteration

[Mx.sup.(k+1)] = [Nx.sup.(k)] for k = 0,1, ...,

where

M = D/[omega], N = (1 - [omega])D/[omega] + L + U

is (block) Jacobi over--relaxation, (B)JOR, and

M = D/[omega] - L, N = (1 - [omega])D/[omega] + U

is (block) successive over--relaxation, (B)SOR. These become point methods when J = n. The convergence for under--relaxation (i.e., [omega] [member of] (0,1)) is well known; in this case, it is also monotonic since the iteration matrices are positive. This is due a result in [2, pp. 270-271] and is proved in a more general setting by Theorem 4.16 in [7]. For w = 1, the iteration matrices are nonnegative. The Jacobi iteration matrix has a zero diagonal and the GS iteration matrix has a zero first column; otherwise, all other elements of these two iteration matrices are positive. Since both iteration matrices have the solution vector as their fixed point (and therefore, an eigenvalue of 1), a sufficient condition for convergence is to show that both iteration matrices do not have other eigenvalues of magnitude 1. Indeed they are as such: the condition for the Jacobi iteration matrix follows for n > 2 from the positivity of its off--diagonal; the condition for the GS iteration matrix follows from the fact that it has a positive submatrix of order (n-1) which is accessible from the excluded first row.

Block iterative methods can be viewed as preconditioned power iterations, where the preconditioning matrix is M [35]. When combined with aggregation steps, they become iterative aggregation--disaggregation (IAD) with BJOR disaggregation step (IAD_BJOR) and BSOR disaggregation step (IAD_BSOR). Because there is an (outer) iteration specified by k, and for each value of k, one needs to solve J subsystems of linear equations directly or iteratively, methods discussed in this subsection are sometimes viewed as being two--level (see also [29]). Although we have implemented and experimented with IAD type methods, they do not yield competitive solvers for Google--like stochastic matrices. Hence, we do not discuss them further in this paper.

In the next section, we present various partitionings that can be used with block iterative solvers.

3. Partitionings for block iterative solvers. Although S > 0, one must work in sparse storage since R is sparse and uv is an outer product; i.e., rank--1 update on R. When R (hence, P) is reducible, an arbitrary partitioning will not yield irreducible diagonal blocks in D. In order to devise effective block iterative solvers, the objective must be to obtain a partitioning of B in which J is relatively low and it is relatively easy to solve the diagonal blocks.

Example 3.1. Let us now consider the nonzero structure of the matrix P of six web pages in Section 2, where an x represents a nonzero value. Recall that B = [alpha][P.sup.T]-I. However, scaling with [alpha] does not change the nonzero structure of [P.sup.T], and we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now, without loss of generality, let us assume that B is permuted to block lower--triangular form having nb irreducible diagonal blocks using Tarjan's algorithm [14] as in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We remark that the irreducible diagonal blocks [F.sub.k,k] for k = 1, 2, ..., nb have zero--free diagonals due to the definition of B and the states incident on each irreducible diagonal block are only fixed up to a permutation.

Example 3.1. (Continued) After applying Tarjan's algorithm to obtain a block lower-triangular matrix for our example, we have the permutation vector [[1 3 2 4 5 6].sup.T]. If we symmetrically permute B with the permutation matrix [[[e.sub.1] [e.sub.3] [e.sub.2] [e.sub.4] [e.sub.5] [e.sub.6]].sup.T], where [e.sub.l] denotes the lth principal axis vector (i.e., lth column of I), we get the nonzero structure

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where nb = 3. The irreducible diagonal blocks correspond to state space partitions {1, 3}, {2}, and {4,5,6}, and they are respectively of order two, one, and three.

It is possible to compute a permutation matrix [Q.sub.k,k] for each irreducible diagonal block [F.sub.k,k] [9] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [T.sub.k,k] is triangular. Note that [T.sub.k,k] is necessarily nonsingular. It is clear that the smaller the order of submatrix [C.sub.k,k] is, the larger the order of submatrix [T.sub.k,k] becomes. Since a triangular block can be solved exactly by using substitution (together with the Sherman--Morrison formula [28] since the block becomes positive due to the addition of the outer product term), it is useful to obtain a larger triangular block. We remark that, under the same permutation, the off--diagonal block [F.sub.k,l] gets permuted as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that [T.sub.k,l] for k [not equal to] l have nothing to do with triangularity.

Minimizing [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be posed as the minimum cutset (or feedback vertex set) problem which is known to be NP--complete for general graphs [22]; therefore, non--optimal solutions need to be considered. Fortunately, a polynomial time algorithm called Cutfind due to Rosen exists [32]. The algorithm runs in linear time and space and finds cutsets of graphs. Although cutsets computed with Cutfind may not be minimum, [9] shows that it is a fast algorithm for large graphs compared to other approximation algorithms and the size of the cutset computed is generally satisfying. We remark that it is again Tarjan's algorithm which is used to find the symmetric permutation that triangularizes the diagonal block associated with the states in the cutset's complement; i.e., [T.sub.k,k]. Thus, for a block triangular matrix having irreducible diagonal blocks with zero--free diagonals, such a (2 x 2) block partitioning can be computed for each diagonal block and substitution can be used for solving the triangular diagonal blocks at each (outer) iteration, while the solution of the remaining diagonal blocks can be approximated with some kind of (inner) point iteration. This approach alleviates the fill--in problem associated with factorizing diagonal blocks in block iterative solvers up to a certain extent.

We consider five partitionings which can be used with block iterative solvers. The first three are based on the idea of symmetrically permuting B to block triangular form and using cutsets to obtain triangular diagonal blocks. The last two partitionings have been already used in the context of MCs before [12] and do not utilize Tarjan's algorithm. They are used to determine whether any improvement over the block iterative process results from employing the first three partitionings. The parameters of the partitionings can be expressed as a Cartesian product of four sets. Let set B = {y,n} denote whether Tarjan's algorithm is used or not, set C = {y,n} denote whether Rosen's Cutfind algorithm is used or not, set R = {y,n} denote whether the number of diagonal blocks is restricted to 2 or not, and set O = {l,u} denote whether a block lower-- or upper--triangular orientation is desired with Tarjan's algorithm. Then experiments with partitionings take as parameters elements from proper subsets of B x C x R x O. Experiments performed on web matrices using partitionings 1 and 2 can utilize elements of {y} x C x R x O. Those using partitioning 3 (in which, through a recursive application of the Tarjan and Cutfind algorithms, all diagonal blocks are made to be triangular) can utilize {y} x {y} x {n} x O. Since partitionings 4 and 5 do not use Tarjan's and Rosen's algorithms, the concept of orientation does not apply, and we arbitrarily set the last parameter to u and say these partitionings utilize the parameters {n} x {n} x {n} x {u}.

Recall that nb is the number of diagonal blocks returned by Tarjan's algorithm for B and let [nb.sub.2] be of those that are of order two. Without loss of generality let us assume that the symmetric permutation is to block lower--triangular form, states incident on each diagonal block are ordered increasingly according to index, and the first state in each diagonal block of order two is placed in the cutset. Keep in mind that it does not make sense to run the Cutfind algorithm on diagonal blocks of order one and two since a diagonal block of order one is already triangular, and either state in a diagonal block of order two forms a triangular diagonal block.

3.1. Partitioning 1. In this partitioning, diagonal blocks of order one with no off-diagonal row elements are placed consecutively in the first diagonal block [T.sub.0,0]. When Cutfind is used, lower--triangular diagonal blocks [T.sub.1,1], [T.sub.2,2], ..., [T.sub.K,K] follow this; the remaining diagonal blocks, which include states of cutsets, are ordered as, [C.sub.K,K], [C.sub.K-1], [K.sub.-1], ..., [C.sub.1,1]. Diagonal blocks of order one, which have some off--diagonal row elements, are grouped into the last block [C.sub.K+1K+1] as in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [l.sub.f] is the indicator function evaluating to 1 when f is true, 0 otherwise, and [E.sub.1(y,y,n,l)] is the corresponding permutation matrix. Note that the diagonal block having [T.sub.0,0],[T.sub.1,1], ..., [T.sub.K,K] along its diagonal is lower--triangular and that it is only this block which is guaranteed to be triangular.

An option for partitioning 1 is to let J = 2 as in (y,y,y,l) so that one has a (2 x 2) block partitioning in which the second diagonal block is comprised of

[C.sub.K,K], [C.sub.K-1,K-1], ..., [C.sub.1,1], [C.sub.K+1,K+1]

along its diagonal. Note that it is not meaningful to restrict the number of diagonal blocks to 2 if the Cutfind algorithm is not used in partitioning 1. Hence, we do not consider partitioning 1 with parameters (y,n,y,l) and (y,n,y,u). A remark must be made at this point about orientation. When a block upper--triangular form is desired with Tarjan's algorithm, diagonal blocks of order one should be checked for zero off--diagonal elements in columns rather than rows and [T.sub.1,1],[T.sub.2,2], ..., [T.sub.K,K] should be upper--triangularized if Cutfind is used.

Example 3.1. (Continued.) Now, let us consider partitioning 1 on our web matrix of 6 pages. Since state 2 is in a state space partition by itself and has nonzero off--diagonal elements in its row, it will be at the end of the permutation. For the first irreducible diagonal block incident on {1,3}, state 1 is an element of the cutset and state 3, being in the cutset's complement, is placed in the first triangular block. After applying the Cutfind algorithm to the irreducible diagonal block incident on {4, 5, 6} of order three, we obtain its cutset as {4} and therefore the cutset's complement as {5,6}. Lower--triangularization of the diagonal block incident on {5,6} using Tarjan's algorithm yields the permutation vector [[5 6].sup.T]. So, the permutation vector becomes [3 5 6 4 1 2]T and the order of the triangular block is obtained as three. Hence, the symmetrically permuted matrix has the nonzero structure in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [E.sub.1(y, y, n,l)] = [[[e.sub.3] [e.sub.5] [e.sub.6] [e.sub.4] [e.sub.1] [e.sub.2]].sup.T]. In this example, K = 2 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. There are four diagonal blocks; the first one is lower--triangular and of order three, the other three are of order one each. Restricting the number of diagonal blocks as in (y,y,y,l) so that we have a (2 x 2) block partitioning in which the first diagonal block is lower--triangular, we obtain the partitioning on the right.

If an upper--triangular orientation is used with partitioning 1, we will end up with the nonzero structure in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [E.sub.1(y,y,n,u)] = [[[E.sub.2][e.sub.6][e.sub.5][e.sub.3][e.sub.1][e.sub.4]].sup.T], K = 2, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Restricting the number of diagonal blocks as in (y,y,y,u) so that we have a (2 x 2) block partitioning in which the first diagonal block is upper--triangular, we obtain the partitioning on the right.

3.2. Partitioning 2. In this partitioning, diagonal blocks of order one are treated as in partitioning 1. Ordering of the remaining diagonal blocks is not changed except for those of order two. When Cutfind is used, for blocks of order two, (arbitrarily) the first state is moved to the first diagonal block [T.sub.0,0], which is lower--triangular, and the second state is moved to the last diagonal block [C.sub.K+1,K+1]. While generating the overall permutation, consecutive processing of diagonal blocks is essential to ensure the lower--triangularity of [T.sub.0,0]. When Cutfind is used, diagonal blocks [T.sub.1,1] [T.sub.2,2], ..., [T.sub.K,K] should be all lower--triangular. In the end, we have a partitioning of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [E.sub.2(y,y,n,l)] is the corresponding permutation matrix. When Cutfind is not used as in (y,n,n,l), we still place the first states of diagonal blocks of order two after the block of states corresponding to states with zero off--diagonal row elements and the second states of diagonal blocks of order two at the end of the permutation but before the block of states corresponding to states with some off--diagonal row elements to see whether there is any merit in this permutation. Recall that partitioning 1 does not handle diagonal blocks of order two as such when Cutfind is not used.

When a block upper--triangular form is desired with Tarjan's algorithm in partitioning 2, diagonal blocks of order one should be checked for zero off--diagonal elements in columns rather than rows as in partitioning 1. Since we do not see any merit in restricting the number of diagonal blocks to 2 in partitioning 2, we do not consider the parameters (y,y,y,l), (y,y,y,u), (y,n,y,l), and (y,n,y,u).

Example 3.1. (Continued.) Now, we consider partitioning 2 on our web matrix of 6 pages. We again place state 2 at the end of the permutation. For the irreducible diagonal block of order two, the first state is placed in the first diagonal block and the second state is placed in the last diagonal block. Since the result of the Cutfind algorithm on the diagonal block of order three is the same as in partitioning 1, state 4 is placed in the cutset and states 5 and 6 are permuted as [[5 6].sup.T] to obtain a lower--triangular diagonal block. The permutation vector becomes [[1 4 5 6 3 2].sup.T] and we have the four diagonal blocks given in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [E.sub.2(y,y,n,l)] = [[[e.sub.1] [e.sub.4] [e.sub.5] [e.sub.6] [e.sub.3] [e.sub.2]].sup.T]. In this example, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the first and the third blocks are lower--triangular.

If an upper--triangular orientation is used with partitioning 2, we will end up with the nonzero structure in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [E.sub.2(y,y,n,u)] = [[[e.sub.2] [e.sub.1] [e.sub.4] [e.sub.6] [e.sub.5] [e.sub.3]].sup.T], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the first and the third blocks are upper--triangular.

Partitionings 1 and 2 do not guarantee that all diagonal blocks are triangular. The next subsection discusses how one can obtain such a partitioning.

3.3. Partitioning 3. This partitioning is obtained with a recursive procedure. A diagonal block considered at a particular recursive call (at the first call, B) is block triangularized using Tarjan's algorithm so that it has irreducible diagonal blocks along its diagonal. Diagonal blocks of order one and two are processed as before without calling the Cutfind algorithm, and the Cutfind algorithm is run on each irreducible diagonal block of order larger than two. In the (2 x 2) block partitionings obtained as such, the non--triangular diagonal blocks associated with the cutsets are grouped together and input to the next recursive call, while blocks associated with the cutset's complements are triangularized and grouped together into a larger triangular block. Recursion ends when each non--triangular diagonal block is of order less than two. We denote the permutation matrix corresponding to partitioning 3 as E3, and remark that the permutation obtained for lower--triangular orientation is the reverse of that of the upper--triangular one.

The implementation of partitioning 3 uses the same data structures and routines as in partitionings 1 and 2 except that it requires three additional integer work arrays having lengths nz, (n + 1), and n, where nz denotes the number of nonzero elements of B. Note that nz less n is [tau]. The first two of these arrays are used for storing the nonzero pattern of the submatrix to be considered at that recursive call and the last one to record the permutation in between recursive calls.

Example 3.1. (Continued.) For partitioning 3, in the first recursive call, after symmetrically permuting B according to the outcome of Tarjan's algorthm, we have three diagonal blocks, the first two of which are of order two and one. So, the Cutfind algorithm need not be executed on them. Therefore, states 1 and 2 are moved to the cutset's complement and state 3 is moved to the cutset. Application of Cutfind to the third irreducible diagonal block yields its cutset as {4}, and therefore the cutset's complement as {5,6}. Lower--triangularization of the diagonal block incident on {5,6} using Tarjan's algorithm gives the permutation vector [[5 6].sup.T]. Hence, the overall permutation vector at the end of the first recursive call is obtained as [[34 1 2 5 6].sup.T]. Restricting the number of diagonal blocks so that we have a (2 x 2) block partitioning in which the second diagonal block of order four is lower--triangular, and in the second recursive call, applying Tarjan's algorithm to the first diagonal block of order two, we obtain two irreducible diagonal blocks of order one each. Therefore, the cutset is the empty set, cutset's complement becomes {3,4}, and recursion ends. Note that now we have a partitioning in which both diagonal blocks are lower--triangular

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [E.sub.3(y,y,n,l)] = [[[e.sub.3] [e.sub.4] [e.sub.1] [e.sub.2] [e.sub.5] [e.sub.6]].sup.T].

If an upper--triangular orientation is used with partitioning 3, we will end up with the nonzero structure in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [E.sub.3(y,y,n,u)] = [[e.sub.6] [e.sub.5] [e.sub.2] [e.sub.1] [e.sub.4] [e.sub.3]].sup.T] and both diagonal blocks are upper--triangular.

3.4. Partitionings 4 and 5. Two straightforward partitionings are considered from [12]. Partitioning equal (here, 4) has [square root of n] diagonal blocks of order [square root of n] if n is a perfect square. If n [not equal to] [[??][square root of n][??].sup.2], there is an extra diagonal block of order n - [[??][square root of n][??].sup.2]. Partitioning other (here, 5) uses diagonal blocks of order respectively 1, 2, 3, .... It has about [square root of n] blocks with the largest diagonal block being of order roughly [square root of n].

When partitionings 1 through 3 are employed with block iterative solvers, [S.sup.T]-I is symmetrically permuted using the corresponding permutation matrix E to obtain the coefficient matrix A. With partitioni Then A is scaled to have a diagonal of 1's and then transformed from point form to block form based on the partitioning chosen. A is transformed to point form and scaled back after the iterations are over.

In Table 3.1, we summarize the way in which the twelve of the fourteen partitionings we have experimented with can be obtained using the permutations suggested by partitionings 1 through 3.

In the next section, we introduce six web matrices, their properties, and the experimental framework.

4. Experimental framework. Different problems resulting from the reducible web matrices Stanford, StanfordBerkeley, Eu2005, WebGoogle, In2004, and WebBase are considered by letting [alpha] [member of] {0.85,0.9,0.95,0.97,0.99}. Hence, altogether there are thirty problems that are analyzed. The Stanford, StanfordBerkeley, and WebGoogle matrices come from the University of Florida Sparse Matrix Collection [8]. All matrices model parts of the hyperlinked web of pages around the world and solving them would rank the pages. The matrices Eu2005 and In2004 are crawled by UbiCrawler [4,26] and uncompressed using the WebGraph [3,39] software. The WebBase matrix is obtained from the Stanford WebBase Project [38]. The six matrices we consider have orders ranging between 281,903 and 2,662,002, and possess dangling nodes. The matrices lack (some) diagonal elements.

Each matrix is obtained from a file which stores in compact sparse row format the matrix columnwise without (some) diagonal entries. In other words, each file stores the nonzero structure of [P.sup.T] in compact sparse row format and must be read as such. The missing diagonal elements are inserted into the corresponding data structures for all solvers except POWER so as to facilitate the construction of B = [R.sup.T] - I. Here we remark that it is possible to implement the point solvers J and GS without forming B as discussed in [13]. A software implementation in the form of a Java code which has done so can be found at [23]. Now, note that the particular sparse format in the files favors POWER in two ways. Since there is no need to transpose [P.sup.T] to work on the rows of P to handle diagonal elements at the outset for POWER, memory for missing diagonal elements and transposition need not be allocated. This is not the case for the other solvers and is also mentioned in [16]. That is, POWER can work by postmultiplying [R.sup.T] = [alpha][P.sup.T] with a column vector at each iteration after [P.sup.T] is read into the compact sparse row format data structure at the outset. This translates to savings in memory and time for POWER. For all the other solvers, we allocate a floatingpoint array to store the diagonal elements of B, scale the rows so that the diagonal elements are all 1 and unscale them back at the end as it is done in the MC analysis software tool MARCA [34]. This saves the flops due to diagonal elements at each iteration. Recall that the software tool [10, 11] also works with irreducible MCs when a is set to 1. Furthermore, each solver including POWER needs at least two floating--point arrays of length n to compute an approximate error norm to test for convergence and the residual norm upon stopping. GS (that is, SOR when the relaxation parameter [omega] is 1) can do with one floating--point array of length n during the iterative process but still needs the second floating--point array for the residual norm computation. However, certain optimizations that improve the memory requirements and timings of our code may be possible. Finally, the routine from [37] that implements Tarjan's algorithm is available for research purposes.

Information regarding the web matrices used in the experiments appears in Table 4.1. The first column provides the matrix name. Columns n and nz' give the order of the matrix and its number of nonzeros as read from the input file. Columns four and five provide its numbers of dangling nodes and missing diagonal elements. Hence, the number of nonzeros in B is given by nz = nz'+ missing diagonal elements. Column nb lists the number of diagonal blocks returned by Tarjan's algorithm on B. Finally, the last column gives the order of the largest one among the nb diagonal blocks. The order of the smallest diagonal block in each matrix is 1 since each matrix has at least one dangling node, and therefore is not listed in the table. Computation of n/nb reveals that the average order of diagonal blocks returned by Tarjan's algorithm is respectively 9.4, 6.3, 9.5, 2.2, 3.8, 2.8 in one decimal digit of precision for the matrices in the given order.

Representative plots of the resulting nonzero structures under the assumed partitionings are provided in Figures 4.1 and 4.2 with the pertaining data interleaved in Tables 4.2-4.7. The nonzero plots of Stanford resemble those of WebGoogle, and the nonzero plots of Stanford--Berkeley, In2004, WebBase resemble those of Eu2005; hence, their nonzero plots are omitted. The number, location, and values of nonzeros in these partitionings have a significant effect on the number of iterations performed by the solvers and their respective solution times. Note, however that the nonzero structure of B, and hence those of its associated partitionings, do not change for different values of a, nor will they change for different personalization vectors v. Hence, time spent at the outset for computing the partitionings can very well be justified if they are not significantly more than the iteration times. In Tables 4.2-4.7, the column "Partitioning" indicates the block partitioning used and lists its parameters. Number of diagonal blocks, order of smallest and largest diagonal blocks, order and number of nonzeros of the first diagonal block, average order and average number of nonzeros of diagonal blocks (both rounded to the nearest integer), number of nonzero elements lying in off--diagonal blocks, and median order of diagonal blocks in the particular partitioning appear in columns J, [min.sub.j] [n.sub.j], [max.sub.j] [n.sub.j], [n.sub.1], [nz.sub.1], E[[n.sub.j]], E[[nz.sub.j]], [nz.sub.off], and [med.sub.j][n.sub.j], Respectively. Note that for partitioning 3, orientation of the block triangular form is immaterial from a statistical point of view of the nonzero structure, and therefore, results only with upper--triangular orientation are reported.

Some observations are due. Among the six web matrices, the nonzero plots of B for

[FIGURE 4.1 OMITTED]

Stanford and WebGoogle (the latter given in Figure 4.2(a) indicate a more uniform distribution of their nonzeros across rows and columns. These two matrices are of different orders, but both look very dense. Note that neither the average order of the diagonal blocks returned by Tarjan's algorithm (9.4 and 2.2, respectively) nor the average number of nonzeros per row (9.2 and 6.6, respectively) is similar for these two matrices. For partitioning 3, the largest percentage of nonzeros within diagonal blocks appear in the Stanford and WebGoogle matrices as well, with about 27% and 32%, respectively. For this partitioning, it is also the same matrices for which the average order of diagonal blocks is largest with about 16,835 and 27,771, respectively. We will see in the next section that these two properties work in favor of partitioning 3 in all of the ten problems associated with these two matrices. On the other hand, the smallest number of nonzeros in the off--diagonal blocks appear in partitioning 1 with parameters (y,n,n,l) in all matrices except WebGoogle and In2004 for which it is a contender. It is clear that this partitioning with Tarjan's algorithm employed to obtain a block lower--triangular form seems to concentrate the largest number of nonzeros within diagonal blocks. We will also see that this is something useful for block iterative methods. Finally, partitioning 4 returns balanced block sizes and always a reasonable number of blocks as intended.

[FIGURE 4.2 OMITTED]

In the next section, we provide the results of numerical experiments on the benchmark matrices.

5. Numerical results. We compare the performance of sparse solvers in the software tool [11] with an emphasis on the memory used, number of iterations taken, accuracy achieved, time for preprocessing and solution. The numerical experiments are performed on a 2.66 GHz Pentium IV processor with 4 GB main memory under the Linux operating system using the o3 optimization level in compiling the code. We provide the results of experiments with three solvers: POWER, GS, and BGS.

The stopping criteria used by all solvers is

k [greater than or equal to] maxit or [[parallel][x.sup.(k)] - [x.sup.(k-1)][parallel].sub.[infinity]] [less than or equal to] stoptol,

where k is the iteration number, maxit is the maximum number of iterations to be performed, and stoptol is the stopping tolerance. The solver BGS also uses the additional criteria

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The use of [stoptol.sub.1] and [stoptol.sub.2] forces the solver to terminate when the norm of the residual is decreasing too slowly, while the differences between two successive iterates is small enough. We let stoptol = [10.sup.-10], [stoptol.sub.1] = [10.sup.-6], and [stoptol.sub.2] = [10.sup.-12], respectively, whereas maxit = 5,000.

For the block iterative methods, the triangular diagonal blocks are solved exactly at each outer iteration with the help of the Shermann--Morrison formula. The remaining diagonal blocks are solved approximately using the corresponding point iterative method. BGS has two additional parameters indicating maximum number and tolerance of inner iterations to be performed with GS for the solution of diagonal blocks. The values of these parameters are respectively elements of the sets {3, 5} and {[10.sup.-3], [10.sup.-5], [10.sup.-10]}. Hence, six experiments are carried out with each of the partitioning parameters except those of partitioning 3, which makes altogether seventy--four experiments for each problem with the BGS solver.

Now, we present our results and then make a general summary. Tables 5.1 through 5.6 provide results from the experiments for each web matrix with [alpha] [member of] {0.85,0.9,0.95,0.97,0.99}. In each table, besides POWER and GS, we have also indicated the BGS solver which gives the minimum total solution time for each partitioning. The column "Solver" indicates the name of the solver and, for BGS solvers, the partitioning used with its parameters. The column "MB" provides the memory requirement of the solver in megabytes. Note that this column includes memory for nonzeros in the matrix and (except POWER) its transpose. The columns "Iterations" and "Residual" give the number of iterations performed and the infinity norm of the residual vector (i.e., [[pi].sup.(k)] - [[pi].sup.(k)]S or - [A.sup.(k)] depending on the solver) upon stopping. The setup time and the total solution time in seconds (s) are given in the next two columns. The setup time includes time for reading the web matrix from the input file, allocating and setting the necessary data structures, and wherever applicable, scaling the coefficient matrix, computing the partitioning, transforming the sparse point representation of the coefficient matrix to a sparse block representation, transforming and scaling it back after the iterations are over. The total solution time is the sum of setup and iteration times. Finally, the last column gives the ratio of the total partitioning time to one iteration time of POWER, rounded to the nearest nonnegative integer. In other words, the column "Ratio" indicates the number of POWER iterations that can be executed during the time the respective partitioning is computed. The bold number shows the best overall total timing result in each table. The identities of winning solvers according to minimum total solution time coincide with those of minimum iteration time in all problems except WebBase with a = 0.85, where it will become BGS with partitioning 1 (y,n,n,l) rather than GS if we consider minimum iteration time. We must remark that it is acceptable for timing results of an experiment obtained by different runs on the same platform to differ by 10-15% due to various effects. The conclusions we derive take this into account.

5.1. Empirical observations. The results show that we can solve the largest and most difficult problem in our suite of thirty problems in less than four minutes on the given platform. The winning solver according to iteration time is always BGS. It is BGS with partitioning 1 in 17 problems, BGS with partitioning 3 in 10 problems, and BGS with partitioning 4 in 3 problems. In general, the time to compute partitionings 1 through 3 are only a fraction of the iteration time if the time to read the matrix and prepare the data structures is excluded from the setup time. That is, partitioning time is roughly equal to the setup time of BGS with the respective partitioning minus the setup time of POWER.

BGS with partitioning 3 and lower--triangular orientation is winner in the Stanford matrix with [alpha] [member of] {0.85,0.9,0.95,0.97}. As reported in Table 5.1, it is also the winner for [alpha] = 0.99, but with upper--triangular orientation. BGS with partitioning 3 is also the winner in the WebGoogle matrix with lower--triangular orientation for [alpha] [member of] {0.85,0.9} and upper-triangular orientation for a G {0.95,0.97,0.99}. For these two web matrices, there seems to be a value of [alpha] beyond which the BGS solver favors upper--triangular orientation with partitioning 3 as the problem becomes more difficult to solve. We remark that we use forward BGS and the block lower--triangular part of A as the preconditioning matrix M. It is that part which multiplies the values of the current approximation. Interestingly, it is only the Stanford and WebGoogle matrices in which partitioning 3 accompanies a winning solver. Not all web matrices need to look the same, and the Stanford matrix may not be a good representative most probably due to its relative smallness. But, partitioning 3 also yields a winning solver with BGS in WebGoogle, which has an order of about a million and significantly different statistical features than Stanford as pointed out in section 4. When BGS is a winner with partitioning 3, the improvements in iteration time compared to the second best solver, GS, and POWER are respectively more than 21%, 47%, and 74%. These correspond to speedups of more than 1.3, 1.9, and 3.8. In Figure 5.1(a), we plot the % change in iteration time of BGS 3 (y,y,n,u) over that of GS for the ten experiments carried out with the Stanford and WebGoogle matrices. The graph shows that the improvement in iteration time is at least 45% for this set of experiments. In general, the time to compute partitioning 3 becomes relatively large compared to those of other partitionings as the order of the matrix increases, due to the relatively large number of recursive calls performed. However, it is still dependent on the value of J, the number of blocks in A, that comes up as a result of the computation. When J is relatively small, the partitioning time will also be relatively small. Note that J equals 42 and 33 with partitioning 3 for the Stanford and WebGoogle matrices, respectively. Although the Cutfind algorithm shortens time per outer iteration, it does so at the expense of an increased number of iterations, and this sets back the total solution time. In any case, partitioning 3 is to be recommended for web matrices having nonzero plots as those of Stanford and WebGoogle, and the larger partitioning time will be clearly offset when the same web matrix is used multiple times.

GS is producing minimum total solution time in the WebBase matrix with [alpha] = 0. 85, but is a runner--up in eleven other problems. However, if minimum iteration time is considered, it is never a winner, and a runner--up only in eight problems. GS consistently reduces the number of iterations with a factor of about 2 over that of POWER and does not have much overhead associated with preprocessing, which make it competitive as observed in the literature before. BGS with partitioning 4 is producing minimum solution time in three problems, namely Eu2005 with [alpha] [member of] {0.95,0.97,0.99}, and performs relatively well in all other problems. When only Tarjan's algorithm is employed, BGS with partitioning 1 is producing minimum total solution time in the remaining sixteen problems (seventeen if minimum iteration time is considered). In fifteen (respectively, sixteen) of those problems, it is the winner with lower--triangular orientation, the exception being In2004 with [alpha] = 0.99. Whenever BGS is the winner with partitioning 1 and parameters (y,n,n,l) or (y,n,n,u), it yields the smallest number of iterations among the solvers in the tables. In all cases for the winning solvers, the stopping tolerance for the inner GS iteration for non--triangular diagonal blocks turns out to be [10.sup.-10]. When BGS 1 (y,n,n,l) 5, [10.sup.-10] is a winner, it reduces the number of iterations over that of POWER with a factor ranging between 7.8 (In2004 with [alpha] = 0.95) to 10.5 (Stanford_Berkeley with [alpha] = 0.99). When BGS 1 (y,n,n,l) 3, [10.sup.-10] is a winner, it reduces the number of iterations over that of POWER with a factor ranging between 4.6 (Stanford_Berkeley with [alpha] = 0.85) to 7.0 (WebBase with [alpha] = 0.97). When BGS is a winner with partitioning 1 (y,n,n,l), the improvements in iteration time compared to POWER are between 44% and 63%. This corresponds to a speedup between 1.8 and 2.7. In Figures 5.1(b) and 5.1(c), we plot the % changes in iteration times of respectively BGS 1 (y,n,n,l) 3, [10.sup.-10] and BGS 1 (y,n,n,l) 5, [10.sup.-10] over that of GS for the thirty experiments performed. The two graphs show that the improvement in iteration time is at least 20% in 60% of the experiments and at least 15% in 70% of the experiments.

We remark that BGS 1 (y,n,n,l) 3, [10.sup.-10] is faster than BGS 1 (y,n,n,l) 3, [10.sup.-3] and BGS 1 (y,n,n,l) 3, [10.sup.-5] in all of the thirty experiments. The improvement in iteration time with BGS 1 (y,n,n,l) 3, [10.sup.-10] over both solvers is at least 25% in 50% of the thirty experiments (results not shown). On the other hand, BGS 1 (y,n,n,l) 5, [10.sup.-10] is slower than BGS 1 (y,n,n,l) 5, [10.sup.-3] and BGS 1 (y,n,n,l) 5, [10.sup.-5] in less than 10% of the thirty experiments. The improvement in iteration time with BGS 1 (y,n,n,l) 5, [10.sup.-10] over both solvers is at least 25% in 50% of the thirty experiments (results not shown). If the performances of BGS 1 (y,n,n,l) 3, [10.sup.-10] and BGS 1 (y,n,n,l) 5, [10.sup.-10] are compared, they come across as being similar.

Among the three solvers we consider in this paper, POWER has the minimum memory requirement, whereas BGS has the highest memory requirement when partitioning 3 is employed. The memory requirement of BGS with partitioning 1 using only Tarjan's algorithm is about twice that of POWER, the memory requirement of BGS with partitioning 3 is about three times that of POWER, and the memory requirement of GS is comparable to that of POWER.

Another set of experiments are conducted by considering symmetric permutations of the six web matrices under study. To this end, ten random permutations for each web matrix is generated using Matlab, thus giving us altogether sixty experiments for [alpha] = 0.85. All of the sixty symmetrically permuted matrices are inspected for their nonzero structures and observed to possess nonzero plots that look uniformly distributed (as in the original versions of the Stanford and WebGoogle matrices). Furthermore, the performance of BGS with partitioning 3 turns out to be insensitive to random symmetric permutations of the input matrix and is much better than that of GS under the same symmetric permutation. It is noticed that GS favors the ordering of web pages in the original versions of the Stanford Berkeley, Eu2005, In 2004, and WebBase matrices. Results of numerical experiments in Figure 5.2 show that BGS with partitioning 3 is always better than BGS 1 (y,n,n,l) 3, [10.sup.-10], which in turn is always better than GS, and the % change in iteration time of BGS with partitioning 3 over that of GS is at least 45%.

To compare the performance of BGS with partitionings 1 (y,n,n,l) and 3 (y,y,n,l) and to test our hypothesis further, two sets of fifty sparse matrices of order 500,000 with densities of 0.625 x [10.sup.-5] and 1.25 x [10.sup.-5] are randomly generated using Matlab. The respective densities yield average numbers of nonzeros of about 4.1 and 7.2 per row including the diagonal element in each matrix. Furthermore, the sparsity patterns of these matrices follow the standard uniform distribution and look like those of Stanford and WebGoogle. Numerical experiments with our tool for [alpha] = 0.85 show that BGS 3 (y,y,n,l) is always faster than BGS 1 (y,n,n,l) 3, [10.sup.-10] and the average improvement in iteration time in the first set of fifty sparse matrices is about 43% and that in the second set of fifty sparse matrices is about 42% (results not shown). These correspond to speedups of 1.8 and 1.7, respectively. More importantly, as depicted in Figures 5.3(a) and 5.3(b), in 90% of the experiments the % change in iteration time of BGS 3 (y,y,n,l) over those of POWER and GS are respectively at least 50% and 40% for the lower density case and 35% and 25% for the higher density case.

[FIGURE 5.1 OMITTED]

[FIGURE 5.2 OMITTED]

6. Conclusion. Various partitionings are considered with block iterative methods for the computation of the steady--state vector of Google--like stochastic matrices in a sequential setting. Some of these partitionings have triangular diagonal blocks, which can be solved directly. Effects of these block partitionings are analyzed through a set of numerical experiments with different values of the teleportation probability in which, among other things, memory requirements and solution times are measured. Time spent at the outset for computing the partitionings are relatively small and can very well be justified when the same web matrix is used multiple times. In general, block Gauss--Seidel with Tarjan's algorithm used to symmetrically permute the sparse term in the coefficient matrix of the system of linear equations to block lower--triangular form, with 3 to 5 point Gauss--Seidel iterations and a stopping tolerance of [10.sup.-10] to solve the diagonal blocks yields the fastest solver. Its memory requirement is about twice that of the power method and it decreases the number of iterations over that of the power method by a factor of more than 4.5. However, for matrices with nonzero plots that look uniformly distributed, a block partitioning with triangular diagonal blocks is to be favored with a lower--triangular orientation for values of [alpha] close to 0.85 and an upper--triangular orientation for values of [alpha] close to 1. Although requiring about three times memory as that of the power method and more time consuming to compute, such a partitioning when accompanying block Gauss--Seidel on such matrices yields iteration time improvements of over 20% compared to the second best solver. Furthermore, it is observed that the performance of block Gauss--Seidel with this partitioning is insensitive to random symmetric permutations of the input matrix (which also have nonzero plots that look uniformly distributed) and is much better than that of Gauss--Seidel under the same symmetric permutation. However, as has been repeatedly observed in the literature, Gauss--Seidel is to be recommended if memory is at a premium. It has comparable memory requirement to that of the power method and reduces the number of iterations over that of the power method by a factor of about 2.

Acknowledgements. The work of the first author is supported by the Turkish Academy of Sciences grant TUBA--GEBIP and that of the second author is supported by The Scientific and Technological Research Council of Turkey. A preliminary version of this work is presented in the Dagstuhl Seminar 07071 "Web Information Retrieval and Linear Algebra Algorithms" in February 2007, and part of the work is carried out at Saarland University where the first author was on sabbatical leave. We thank the two anonymous referees for their remarks and pointing out some of the references, and the second referee especially for encouraging us to consider random symmetric permutations, which led to an improved manuscript.

[FIGURE 5.3 OMITTED]

REFERENCES

[1] A. ARASU, J. NOVAK, A. S. TOMKINS, and J. A. TOMLIN, PageRank computation and the structure of the web: Experiments and algorithms, in Proceedings of the 11th International Conference on World Wide Web, Honolulu, Hawaii, 2002, Poster Track. http://www2002.org/CDROM/poster/173.pdf

[2] R. BELLMAN, Introduction to Matrix Analysis, 2nd ed., SIAM, Philadelphia, Pennsylvania, 1997.

[3] P. BOLDI and S. VIGNA, The WebGraph Framework I: Compression Techniques, in Proceedings of the 13th International Conference on World Wide Web, New York, ACM, 2004, pp. 595-601.

[4] P. BOLDI, B. CODENOTTI, M. SANTINI, and S. VIGNA, UbiCrawler: A Scalable Fully Distributed Web Crawler, Software: Practice & Experience, 34 (2004), pp. 711-726.

[5] S. BRIN And L. PAGE, The anatomy of a large-scale hypertextual web search engine, Computer Networks and ISDN Systems, 30 (1998), pp. 107-117.

[6] A. Z. BRODER, R. LEMPEL, F. MAGHOUL, And J. PEDERSEN, Efficient PageRank approximation via graph aggregation, Inform. Retrieval, 9 (2006), pp. 123-138.

[7] P. BUCHHOLZ and T. DAYAR, On the convergence of a class of multilevel methods for large, sparse Markov chains, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 1025-1049

[8] T. DAVIS, University of Florida Sparse Matrix Collection, 2011, NA Digest, 92, no. 42, October 16, 1994, NA Digest, 96, no. 28, July 23, 1996, and NA Digest, 97, no. 23, June 7, 1997. http://www.cise.ufl.edu/research/sparse/matrices.

[9] T. DAYAR, Obtaining triangular diagonal blocks using cutsets, Technical Report BU-CE-0701, Department of Computer Engineering, Bilkent University, Ankara, Turkey, January 2007. http://www.cs.bilkent.edu.tr/tech-reports/2 0 07/BU-CE- 07 01.pdf

[10] T. DAYAR And G. N. NOYAN, A software tool for the steady-state analysis of Google-like stochastic matrices, in Proceeding of the Fourth International ICST Conference on Performance Evaluation Methodologies and Tools, Workshop on Tools for Solving Structured Markov Chains, Eds. B. Meini, A. Horvath, ICST, Brussels, Belgium, 2009, Article No. 14.

[11] __, Software for the steady-state analysis of Google-like stochastic matrices, 2011. http://www.cs.bilkent.edu.tr/~tugrul/software.html

[12] T. DAYAR And W. J. STEWART, Comparison of partitioning techniques on two-level iterative solvers on large, sparse Markov chains, SIAM J. Sci. Comput., 21 (2000), pp. 1691-1705.

[13] G. M. DEL CORSO, A. GULLI, And F. ROMANI, Fast PageRank computation via a sparse linear system, Internet Math., 2 (2005), pp. 251-273.

[14] I. S. DUFF and J. K. REID, An implementation of Tarjan's algorithm for the block triangularization of a matrix, ACM Trans. Math. Software, 4 (1978), pp. 137-147.

[15] N. EIRON, K. S. Mccurley, And J. A. TOMLIN, Ranking the web frontier, in Proceedings of the 13th International Conference on World Wide Web, New York, ACM, 2004, pp. 309-318. http://research.yahoo.com/files/1p309.pdf

[16] D. F. GLEICH, A. P. GRAY, C. GREIF, And T. LAU, An inner-outer iteration for PageRank, SIAM J. Sci. Comput., 32 (2010), pp. 349-371.

[17] G. H. GOLUB And C. GREIF, An Arnoldi-type algorithm for computing Page Rank, BIT Numer. Math., 46 (2006), pp. 759-771.

[18] T. H. HAVELIWALA And S. D. KAMVAR, The second eigenvalue of the Google matrix, Technical Report 2003-20, Stanford University, 2003. http://ilpubs.stanford.edu:8090/582/1/2003-20.pdf

[19] I. C. F. IPSEN and T. M. SELEE, PageRank computation, with special attention to dangling nodes, SIAM J. Matrix Anal. Appl., 28 (2007), pp. 1281-1296.

[20] S. D. KAMVAR, T. H. HAVELIWALA, C. D. MANNING, and G. H. GOLUB, Extrapolation methods for accelerating PageRank computations, in Proceedings of the 12th International Conference on World Wide Web, Budapest, Hungary, 2003, pp. 261-270.

[21] --, Exploiting the block structure of the web for computing PageRank, Technical Report 2003-17, Stan- ford University, 2003. http://ilpubs.stanford.edu:8 090/579/1/2 003-17.pdf

[22] R. M. KARP, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85-103.

[23] Laboratory of Web Algorithms Software, 2011. http://law.dsi.unimi.it/software.php

[24] A. N. LANGVILLE And C. D. MEYER, Deeper inside PageRank, Internet Math., 1 (2004), pp. 335-380.

[25] --, A reordering for the PageRank problem, SIAM J. of Sci. Comput., 27 (2006), pp. 2112-2120.

[26] Larbin home page, 2011. http://larbin,sourceforge.net/index-eng.html

[27] F. MCSHERRY, A uniform approach to accelerated PageRank computation, in the Proceedings of the 14th International Conference on the World Wide Web, Chiba, Japan, ACM, 2005, pp. 575-582.

[28] C. D. MEYER, Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, 2000.

[29] V. MIGALLON, J. PENADES, and D. B. SZYLD, Block two-stage methods for singular systems and Markov chains, Numer. Linear Algebra Appl., 3 (1996), pp. 413-426.

[30] G. N. NOYAN, Steady-state analysis of Google-like matrices, M.S. Thesis, Department of Computer Engineering, Bilkent University, Ankara, Turkey, September 2007.

[31] I. PULTAROVA, Tarjan's algorithm in computing PageRank, in the 13th Annual Conference Proceedings of Technical Computing Prague, C. Moler, A. Prochazka, and B. Walden, eds., VSCHT, Prague, Czech Republic, 2005.

[32] B. K. ROSEN, Robust linear algorithms for cutsets, J. Algorithms, 3 (1982), pp. 205-217.

[33] S. SERRA-CAPIZZANO, Jordan canonical form of the Google matrix: A potential contribution to the PageRank computation, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 305-312.

[34] W. J. STEWART, MARCA: Markov chain analyzer, in Numerical Solution of Markov Chains, W. J. Stewart, ed., Marcel Dekker, New York, 1991, pp. 687-690.

[35] __, Introduction to the Numerical Solution of Markov Chains, Princeton University Press, Princeton, 1994.

[36] R. E. TARJAN, Depth-first search and linear graph algorithms, SIAM J. Comput., 1 (1972), pp. 146-160.

[37] The HSL Mathematical Software Library, 2011. http://www .hsl.rl.ac. uk/

[38] The Stanford WebBase Project, 2011. http ://diglib.stanford.edu:8 091/~testbed/doc2/WebBase/

[39] Webgraph, 2011. http://webgraph.dsi.unimi.it

TUGRUL DAYAR ([dagger]) and GOKCE N. NOYAN ([double dagger)

* Received April 12, 2010. Accepted for publication January 17, 2011. Published online March 28, 2011. Recommended by M. Benzi.

([dagger]) Department of Computer Engineering, Bilkent University, TR--06800 Bilkent, Ankara, Turkey (tugrul@cs .bilkent. edu. tr).

([double dagger])Undersecretariat for Defence Industries, Ziyabey Caddesi, 21 Sokak, No.4, TR--06520 Balgat, Ankara, Turkey (gnnoyan@ssm.gov. tr).
TABLE 3.1
Obtaining partitionings 1 through 3 on B.

Partitioning       Steps

1 (y,y,n,l)    (1) Apply Tarjan's algorithm to obtain block
                   lower-triangular form.

               (2) Move states of diagonal blocks of order one with
                   zero off-diagonal row elements to beginning, those
                   with some off-diagonal row elements to end of
                   permutation.

               (3) Apply the Cutfind algorithm to each diagonal block
                   of order larger than two; move states in cutset's
                   complement towards beginning and states in cutset
                   towards end of permutation; lower-triangularize
                   diagonal block of states in cutset's complement;
                   for diagonal blocks of order two, move first state
                   towards end and second state towards beginning of
                   permutation.

               (4) All states moved towards beginning of permutation
                   form first (lower-triangular) diagonal block; all
                   other subsets of states moved towards end of
                   permutation form remaining diagonal blocks.

1 (y,y,n,u)        As in 1 (y,y,n,l) except 'lower' and 'row' are
                   replaced with 'upper' and 'column'.

1 (y,y,y,l)        As in 1 (y,y,n,l) except step (4) is changed such
                   that all other subsets of states moved towards end
                   of permutation form second diagonal block.

1 (y,y,y,u)        As in 1 (y,y,n,u) except step (4) is changed such
                   that all other subsets of states moved towards end
                   of permutation form second diagonal block.

1 (y,n,n,l)        As in 1 (y,y,n,l) except step (3) is omitted.

1 (y, n,n,u)       As in 1 (y,y,n,u) except step (3) is omitted.

2 (y,y,n,l)    (1) As in step (1) of 1 (y,y,n,l).

               (2) As in step (2) of 1 (y,y,n,l).

               (3) For diagonal blocks of order two, move first state
                   towards beginning of permutation and second state
                   towards end of permutation.

               (4) Apply the Cutfind algorithm to each diagonal block
                   of order larger than two; move states in cutset's
                   complement towards beginning and states of
                   cutset  to end of states in diagonal block;
                   lower-triangularize diagonal block of states in
                   cutset's complement.

               (5) All states moved towards beginning of permutation
                   form first (lower-triangular) diagonal block; all
                   other subsets of states form remaining diagonal
                   blocks.

2 (y,y,n,u)        As in 2 (y,y,n,l) except 'lower' and 'row' are
                   replaced with 'upper' and 'column'.

2 (y,n,n,l)        As in 2 (y,y,n,l) except step (4) is omitted and
                   step (5) is changed such that only states moved to
                   beginning of permutation in step (2) form first
                   (lower-triangular) diagonal block; all other
                   subsets of states form remaining diagonal blocks.

2 (y, n,n,u)       As in 2 (y,y,n,u) except step (4) is omitted and
                   step (5) is changed such that only states moved to
                   beginning of permutation in step (2) form first
                   (upper-triangular) diagonal block; all other
                   subsets of states form remaining diagonal blocks.

3 (y,y,n,l)    Recursively:

               (1) Apply Tarjan's algorithm to obtain block
                   lower-triangular form.

               (2) Process diagonal blocks of order one and two
                   without calling the Cutfind algorithm.

               (3) Apply the Cutfind algorithm to all other diagonal
                   blocks.

               (4) Lower-triangularize diagonal blocks associated with
                   cutsets' complements and group them together into a
                   larger triangular block.

               (5) If there is a cutset with more than one state,
                   group states associated with cutsets together and
                   make a recursive call with corresponding diagonal
                   block.

3 (y,y,n,u)        As in 3 (y,y,n,l) except 'lower' is replaced with
                   'upper'.

TABLE 4.1
Properties of web matrices.

                                                   dangling
Matrix                       n            nz'         nodes

Stanford               281,903      2,312,497        20,315
StanfordBerkeley       683,446      7,583,376        68,062
Eu2005                 862,664     19,235,140        71,675
WebGoogle              916,428      5,105,039       176,974
In2004               1,382,908     16,917,053            86
WebBase              2,662,002     44,843,770       574,863

                                                   order of
                       missing                      largest
                      diagonal                     diagonal
Matrix                elements             nb         block

Stanford               281,903         29,914       150,532
StanfordBerkeley       683,446        109,238       333,752
Eu2005                 361,237         90,768       752,725
WebGoogle              916,428        412,479       434,818
In2004               1,005,498        367,675       593,687
WebBase              2,662,002        954,137     1,390,621

TABLE 4.2
Nonzero structure of the partitionings on B for the Stanford matrix.

                                    [min.sub.j]      [max.sub.j]
Partitioning                 J        [n.sub.j]        [n.sub.j]

1 (y,y,n,l)              3,520                1          159,037
1 (y,y,n,u)              3,520                1          179,180
1 (y,y,y,l)                  2          122,866          159,037
1 (y,y,y,u)                  2          102,723          179,180
1 (y,n,n,l)              3,520                2          150,532
1 (y,n,n,u)              3,520                2          150,532
2 (y,y,n,l)              4,776                1          100,162
2 (y,y,n,u)              4,776                1          100,162
2 (y,n,n,l)              3,520                1          150,532
2 (y,n,n,u)              3,520                1          150,532
3 (y,y,n,u)                 42                1          185,332
4 (n,n,n,u)                531              530            1,003
5 (n,n,n,u)                751                1              750

Partitioning         [n.sub.i]       [nz.sub.i]     E[[n.sub.j]]

1 (y,y,n,l)            159,037          452,823               80
1 (y,y,n,u)            179,180          517,281               80
1 (y,y,y,l)            159,037          452,823          140,952
1 (y,y,y,u)            179,180          517,281          140,952
1 (y,n,n,l)                172              172               80
1 (y,n,n,u)             20,315           20,315               80
2 (y,y,n,l)              1,303            1,356               59
2 (y,y,n,u)             21,446           21,569               59
2 (y,n,n,l)                172              172               80
2 (y,n,n,u)             20,315           20,315               80
3 (y,y,n,u)            185,332          555,177            6,712
4 (n,n,n,u)                530              534              531
5 (n,n,n,u)                  1                1              375

                                                     [med.sub.j]
Partitioning     E[[nz.sub.j]]     [nz.sub.off]        [n.sub.j]

1 (y,y,n,l)                332        1,425,977                2
1 (y,y,n,u)                339        1,401,385                2
1 (y,y,y,l)            650,834        1,292,733          140,952
1 (y,y,y,u)            608,351        1,377,698          140,952
1 (y,n,n,l)                673          224,891                6
1 (y,n,n,u)                668          244,614                6
2 (y,y,n,l)                241        1,441,346                6
2 (y,y,n,u)                237        1,461,074                6
2 (y,n,n,l)                673          226,848                6
2 (y,n,n,u)                667          246,646                6
3 (y,y,n,u)             16,845        1,886,918               52
4 (n,n,n,u)                538        2,308,602              530
5 (n,n,n,u)                380        2,308,739              375

TABLE 4.3
Nonzero structure of the partitionings on B for the Stanford-Berkeley
matrix.

                                    [min.sub.j]      [max.sub.j]
Partitioning                 J        [n.sub.j]        [n.sub.j]

1 (y,y,n,l)              6,750                1          360,788
1 (y,y,n,u)              6,750                1          424,115
1 (y,y,y,l)                  2          322,658          360,788
1 (y,y,y,u)                  2          259,331          424,115
1 (y,n,n,l)              6,750                2          333,752
1 (y,n,n,u)              6,750                2          333,752
2 (y,y,n,l)             10,116                1          227,157
2 (y,y,n,u)             10,116                1          227,157
2 (y,n,n,l)              6,750                1          333,752
2 (y,n,n,u)              6,750                1          333,752
3 (y,y,n,u)                163                2          458,614
4 (n,n,n,u)                827              826            1,170
5 (n,n,n,u)              1,169                1            1,168

Partitioning         [n.sub.i]       [nz.sub.i]     E[[n.sub.j]]

1 (y,y,n,l)            360,788        1,013,364              101
1 (y,y,n,u)            424,115        1,195,425              101
1 (y,y,y,l)            360,788        1,013,364          341,723
1 (y,y,y,u)            424,115        1,195,425          341,723
1 (y,n,n,l)              4,735            4,735              101
1 (y,n,n,u)             68,062           68,062              101
2 (y,y,n,l)              6,426            6,484               68
2 (y,y,n,u)             69,753           69,870               68
2 (y,n,n,l)              4,735            4,735              101
2 (y,n,n,u)             68,062           68,062              101
3 (y,y,n,u)            458,614        1,719,076            4,193
4 (n,n,n,u)                826            4,340              826
5 (n,n,n,u)                  1                1              585

                                                     [med.sub.j]
Partitioning     E[[nz.sub.j]]     [nz.sub.off]        [n.sub.j]

1 (y,y,n,l)                601        4,208,017                3
1 (y,y,n,u)                553        4,534,222                3
1 (y,y,y,l)          2,348,303        3,570,216          341,723
1 (y,y,y,u)          1,975,004        4,316,815          341,723
1 (y,n,n,l)              1,087          926,824                6
1 (y,n,n,u)              1,021        1,371,763                6
2 (y,y,n,l)                398        4,239,810                5
2 (y,y,n,u)                354        4,685,016                5
2 (y,n,n,l)              1,087          928,567                6
2 (y,n,n,u)              1,021        1,373,832                6
3 (y,y,n,u)             12,946        6,156,597               10
4 (n,n,n,u)              4,931        4,188,520              826
5 (n,n,n,u)              3,465        4,216,462              585

TABLE 4.4
Nonzero structure of the partitionings on B for the Eu2005 matrix.

                                    [min.sub.j]      [max.sub.j]
Partitioning                 J        [n.sub.j]        [n.sub.j]

1 (y,y,n,l)              1,162                1          465,433
1 (y,y,n,u)              1,163                1          546,874
1 (y,y,y,l)                  2          397,231          465,433
1 (y,y,y,u)                  2          315,790          546,874
1 (y,n,n,l)              1,162                2          752,725
1 (y,n,n,u)              1,163                2          752,725
2 (y,y,n,l)              1,588                1          451,763
2 (y,y,n,u)              1,588                1          451,763
2 (y,n,n,l)              1,162                1          752,725
2 (y,n,n,u)              1,163                1          752,725
3 (y,y,n,u)                378                1          555,044
4 (n,n,n,u)                929              928            1,480
5 (n,n,n,u)              1,314                1            1,313

Partitioning         [n.sub.i]       [nz.sub.i]     E[[n.sub.j]]

1 (y,y,n,l)            465,433        1,354,607              742
1 (y,y,n,u)            546,874        1,875,258              742
1 (y,y,y,l)            465,433        1,354,607          431,332
1 (y,y,y,u)            546,874        1,875,258          431,332
1 (y,n,n,l)            752,725       18,201,086              742
1 (y,n,n,u)             81,441           81,441              742
2 (y,y,n,l)                368              382              543
2 (y,y,n,u)             81,809           82,067              543
2 (y,n,n,l)            752,725       18,201,086              742
2 (y,n,n,u)             81,441           81,441              742
3 (y,y,n,u)            555,044        1,942,183            2,282
4 (n,n,n,u)                928           11,808              929
5 (n,n,n,u)                  1                1              657

                                                     [med.sub.j]
Partitioning     E[[nz.sub.j]]     [nz.sub.off]        [n.sub.j]

1 (y,y,n,l)              9,087        9,028,274                2
1 (y,y,n,u)              9,452        8,603,667                2
1 (y,y,y,l)          5,618,481        8,359,415          431,332
1 (y,y,y,u)          5,516,566        8,563,246          431,332
1 (y,n,n,l)             15,867        1,158,774                3
1 (y,n,n,u)             15,841        1,173,377                3
2 (y,y,n,l)              6,654        9,029,473                2
2 (y,y,n,u)              6,645        9,043,989                2
2 (y,n,n,l)             15,867        1,158,974                3
2 (y,n,n,u)             15,841        1,173,734                3
3 (y,y,n,u)              6,713       17,058,750                1
4 (n,n,n,u)              7,829       12,322,997              928
5 (n,n,n,u)              5,424       12,469,660              656

TABLE 4.5
Nonzero structure of the partitionings on B for the WebGoogle matrix.

                                    [min.sub.j]      [max.sub.j]
Partitioning                 J        [n.sub.j]        [n.sub.j]

1 (y,y,n,l)             12,876                1          524,850
1 (y,y,n,u)             12,876                1          499,941
1 (y,y,y,l)                  2          391,578          524,850
1 (y,y,y,u)                  2          416,487          499,941
1 (y,n,n,l)             12,876                2          434,818
1 (y,n,n,u)             12,876                2          434,818
2 (y,y,n,l)             17,412                1          280,066
2 (y,y,n,u)             17,412                1          280,066
2 (y,n,n,l)             12,876                1          434,818
2 (y,n,n,u)             12,876                1          434,818
3 (y,y,n,u)                 33                1          722,666
4 (n,n,n,u)                958              579              957
5 (n,n,n,u)              1,354                1            1,353

Partitioning         [n.sub.i]       [nz.sub.i]     E[[n.sub.j]]

1 (y,y,n,l)            524,850        1,057,698               71
1 (y,y,n,u)            499,941          966,216               71
1 (y,y,y,l)            524,850        1,057,698          458,214
1 (y,y,y,u)            499,941          966,216          458,214
1 (y,n,n,l)            201,883          201,883               71
1 (y,n,n,u)            176,974          176,974               71
2 (y,y,n,l)            206,052          216,382               53
2 (y,y,n,u)            181,143          182,884               53
2 (y,n,n,l)            201,883          201,883               71
2 (y,n,n,u)            176,974          176,974               71
3 (y,y,n,u)            722,666        1,640,818           27,771
4 (n,n,n,u)                957              957              957
5 (n,n,n,u)                  1                1              677

                                                     [med.sub.j]
Partitioning     E[[nz.sub.j]]     [nz.sub.off]        [n.sub.j]

1 (y,y,n,l)                234        3,013,372                1
1 (y,y,n,u)                228        3,079,757                1
1 (y,y,y,l)          1,624,343        2,772,781          458,214
1 (y,y,y,u)          1,783,650        2,454,168          458,214
1 (y,n,n,l)                371        1,243,063                4
1 (y,n,n,u)                371        1,242,875                4
2 (y,y,n,l)                163        3,189,056                2
2 (y,y,n,u)                163        3,189,011                2
2 (y,n,n,l)                371        1,247,096                4
2 (y,n,n,u)                371        1,238,462                4
3 (y,y,n,u)             58,624        4,086,863              299
4 (n,n,n,u)                962        5,099,746              957
5 (n,n,n,u)                681        5,099,941              676

TABLE 4.6
Nonzero structure of the partitionings on B for the In2004 matrix.

                                    [min.sub.j]      [max.sub.j]
Partitioning                 J        [n.sub.j]        [n.sub.j]

1 (y,y,n,l)             16,644                1          929,778
1 (y,y,n,u)             16,644                1          635,092
1 (y,y,y,l)                  2          453,130          929,778
1 (y,y,y,u)                  2          635,092          747,816
1 (y,n,n,l)             16,644                2          593,687
1 (y,n,n,u)             16,644                2          593,687
2 (y,y,n,l)             26,978                1          384,611
2 (y,y,n,u)             26,978                1          384,611
2 (y,n,n,l)             16,644                1          593,687
2 (y,n,n,u)             16,644                1          593,687
3 (y,y,n,u)                474                1          986,091
4 (n,n,n,u)              1,176            1,175            2,283
5 (n,n,n,u)              1,663                1            1,662

Partitioning         [n.sub.i]       [nz.sub.i]     E[[n.sub.j]]

1 (y,y,n,l)            929,778        2,573,755               83
1 (y,y,n,u)            635,092        1,745,311               83
1 (y,y,y,l)            929,778        2,573,755          691,454
1 (y,y,y,u)            635,092        1,745,311          691,454
1 (y,n,n,l)            294,780          294,780               83
1 (y,n,n,u)                 94               94               83
2 (y,y,n,l)            297,934          305,915               51
2 (y,y,n,u)              3,248            3,297               51
2 (y,n,n,l)            294,780          294,780               83
2 (y,n,n,u)                 94               94               83
3 (y,y,n,u)            986,091        2,965,885            2,918
4 (n,n,n,u)              1,175           31,832            1,176
5 (n,n,n,u)                  1                1              832

                                                     [med.sub.j]
Partitioning     E[[nz.sub.j]]     [nz.sub.off]        [n.sub.j]

1 (y,y,n,l)                641        7,259,360                4
1 (y,y,n,u)                619        7,618,442                4
1 (y,y,y,l)          5,427,036        7,068,479          691,454
1 (y,y,y,u)          5,408,008        7,106,534          691,454
1 (y,n,n,l)                992        1,413,736                7
1 (y,n,n,u)              1,002        1,239,060                7
2 (y,y,n,l)                375        7,809,139                4
2 (y,y,n,u)                381        7,663,801                4
2 (y,n,n,l)                992        1,413,651                7
2 (y,n,n,u)              1,003        1,230,381                7
3 (y,y,n,u)              7,584       14,327,904               11
4 (n,n,n,u)              9,404        6,863,176            1,175
5 (n,n,n,u)              6,615        6,922,088              832

TABLE 4.7
Nonzero structure of the partitionings on B for the WebBase matrix.

                                    [min.sub.j]      [max.sub.j]
Partitioning                 J        [n.sub.j]        [n.sub.j]

1 (y,y,n,l)              8,584                1        1,635,593
1 (y,y,n,u)              8,584                1        1,854,996
1 (y,y,y,l)                  2        1,026,409        1,635,593
1 (y,y,y,u)                  2          807,006        1,854,996
1 (y,n,n,l)              8,584                2        1,390,621
1 (y,n,n,u)              8,584                2        1,390,621
2 (y,y,n,l)             10,188                1        1,054,569
2 (y,y,n,u)             10,188                1        1,054,569
2 (y,n,n,l)              8,584                1        1,390,621
2 (y,n,n,u)              8,584                1        1,390,621
3 (y,y,n,u)                404                1        2,225,698
4 (n,n,n,u)              1,632            1,631            1,841
5 (n,n,n,u)              2,307                1            2,306

Partitioning         [n.sub.i]       [nz.sub.i]     E[[n.sub.j]]

1 (y,y,n,l)          1,635,593        5,085,941              310
1 (y,y,n,u)          1,854,996        6,049,826              310
1 (y,y,y,l)          1,635,593        5,085,941        1,331,001
1 (y,y,y,u)          1,854,996        6,049,826        1,331,001
1 (y,n,n,l)            355,460          355,460              310
1 (y,n,n,u)            574,863          574,863              310
2 (y,y,n,l)            358,949          362,330              261
2 (y,y,n,u)            578,352          585,200              261
2 (y,n,n,l)            355,460          355,460              310
2 (y,n,n,u)            574,863          574,863              310
3 (y,y,n,u)          2,225,698        8,197,002            6,589
4 (n,n,n,u)              1,631           50,035            1,631
5 (n,n,n,u)                  1                1            1,154

                                                     [med.sub.j]
Partitioning     E[[nz.sub.j]]     [nz.sub.off]        [n.sub.j]

1 (y,y,n,l)              2,030       30,079,285                1
1 (y,y,n,u)              2,104       29,445,974                1
1 (y,y,y,l)          9,542,739       28,420,294        1,331,001
1 (y,y,y,u)         11,578,808       24,348,156        1,331,001
1 (y,n,n,l)              4,541        8,523,737                3
1 (y,n,n,u)              4,528        8,634,908                3
2 (y,y,n,l)              1,655       30,647,129                4
2 (y,y,n,u)              1,644       30,755,389                4
2 (y,n,n,l)              4,541        8,524,636                3
2 (y,n,n,u)              4,528        8,636,363                3
3 (y,y,n,u)             21,962       38,633,180               10
4 (n,n,n,u)             11,114       29,368,144            1,631
5 (n,n,n,u)              7,675       29,799,021            1,154

TABLE 5.1
Results for the Stanford matrix.

[alpha]    Solver                                    MB    Iterations

0.85       POWER                                     38           103
           GS                                        50            45
           BGS 1 (y,n,n,l) 3, [10.sup.-10]           86            18
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           110            42
           BGS 3 (y,y,n,l)                          122            44
           BGS 4 (n,n,n,u) 3, [10.sup.-3]            86            45
           BGS 5 (n,n,n,u) 5, [10.sup.-3]            86            45

0.9        POWER                                     38           154
           GS                                        50            65
           BGS 1 (y,n,n,l) 3, [10.sup.-10]           86            26
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           110            62
           BGS 3 (y,y,n,l)                          122            63
           BGS 4 (n,n,n,u) 3, [10.sup.-3]            86            65
           BGS 5 (n,n,n,u) 3, [10.sup.-3]            86            65

0.95       POWER                                     38           288
           GS                                        50           124
           BGS 1 (y,n,n,l) 3, [10.sup.-10]           86            45
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           110           118
           BGS 3 (y,y,n,l)                          122           117
           BGS 4 (n,n,n,u) 3, [10.sup.-3]            86           124
           BGS 5 (n,n,n,u) 5, [10.sup.-3]            86           124

0.97       POWER                                     38           475
           GS                                        50           201
           BGS 1 (y,n,n,l) 5, [10.sup.-10]           86            43
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           110           192
           BGS 3 (y,y,n,l)                          122           191
           BGS 4 (n,n,n,u) 5, [10.sup.-3]            86           201
           BGS 5 (n,n,n,u) 3, [10.sup.-3]            86           201

0.99       POWER                                     38         1,319
           GS                                        50           574
           BGS 1 (y,y,y,l) 3, [10.sup.-3]           108           566
           BGS 2 (y,y,n,u) 3, [10.sup.-3]           110           588
           BGS 3 (y,y,n,u)                          122           552
           BGS 4 (n,n,n,u) 3, [10.sup.-3]            86           574
           BGS 5 (n,n,n,u) 5, [10.sup.-3]            86           574

[alpha]    Solver                              Residual     Setup (s)

0.85       POWER                                8.4e-11           1.2
           GS                                   5.9e-11           1.3
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      9.2e-11           2.5
           BGS 2 (y,y,n,l) 3, [10.sup.-3]       6.4e-11           3.0
           BGS 3 (y,y,n,l)                      5.3e-11           3.1
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       5.9e-11           1.8
           BGS 5 (n,n,n,u) 5, [10.sup.-3]       5.9e-11           1.8

0.9        POWER                                7.6e-11           1.3
           GS                                   7.5e-11           1.4
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      7.1e-11           2.5
           BGS 2 (y,y,n,l) 3, [10.sup.-3]       7.2e-11           3.0
           BGS 3 (y,y,n,l)                      7.0e-11           3.1
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       7.5e-11           1.8
           BGS 5 (n,n,n,u) 3, [10.sup.-3]       7.5e-11           1.6

0.95       POWER                                9.1e-11           1.2
           GS                                   8.6e-11           1.4
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      7.6e-11           2.5
           BGS 2 (y,y,n,l) 3, [10.sup.-3]       8.2e-11           2.9
           BGS 3 (y,y,n,l)                      8.8e-11           3.2
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       8.6e-11           1.8
           BGS 5 (n,n,n,u) 5, [10.sup.-3]       8.6e-11           1.8

0.97       POWER                                9.6e-11           1.2
           GS                                   9.0e-11           1.4
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      8.6e-11           2.4
           BGS 2 (y,y,n,l) 3, [10.sup.-3]       9.0e-11           3.1
           BGS 3 (y,y,n,l)                      9.3e-11           3.2
           BGS 4 (n,n,n,u) 5, [10.sup.-3]       9.0e-11           1.7
           BGS 5 (n,n,n,u) 3, [10.sup.-3]       9.0e-11           1.7

0.99       POWER                                9.9e-11           1.2
           GS                                   5.6e-11           1.4
           BGS 1 (y,y,y,l) 3, [10.sup.-3]       5.4e-11           3.0
           BGS 2 (y,y,n,u) 3, [10.sup.-3]       9.6e-11           3.0
           BGS 3 (y,y,n,u)                      7.4e-11           3.1
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       5.6e-11           1.8
           BGS 5 (n,n,n,u) 5, [10.sup.-3]       5.6e-11           1.7

[alpha]    Solver                             Total (s)         Ratio

0.85       POWER                                   10.1
           GS                                       5.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          5.5            15
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           5.4            21
           BGS 3 (y,y,n,l)                          4.9            22
           BGS 4 (n,n,n,u) 3, [10.sup.-3]           6.2             7
           BGS 5 (n,n,n,u) 5, [10.sup.-3]           6.2             7

0.9        POWER                                   14.3
           GS                                       8.0
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          6.9            14
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           6.6            20
           BGS 3 (y,y,n,l)                          5.7            21
           BGS 4 (n,n,n,u) 3, [10.sup.-3]           8.1             6
           BGS 5 (n,n,n,u) 3, [10.sup.-3]           8.0             4

0.95       POWER                                   25.6
           GS                                      13.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         10.3            15
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           9.8            17
           BGS 3 (y,y,n,l)                          8.0            24
           BGS 4 (n,n,n,u) 3, [10.sup.-3]          13.9             7
           BGS 5 (n,n,n,u) 5, [10.sup.-3]          13.9             7

0.97       POWER                                   41.4
           GS                                      21.7
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         14.2            14
           BGS 2 (y,y,n,l) 3, [10.sup.-3]          14.1            22
           BGS 3 (y,y,n,l)                         11.1            24
           BGS 4 (n,n,n,u) 5, [10.sup.-3]          21.3             6
           BGS 5 (n,n,n,u) 3, [10.sup.-3]          21.4             6

0.99       POWER                                  112.5
           GS                                      59.3
           BGS 1 (y,y,y,l) 3, [10.sup.-3]          35.0            21
           BGS 2 (y,y,n,u) 3, [10.sup.-3]          36.2            21
           BGS 3 (y,y,n,u)                         25.8            23
           BGS 4 (n,n,n,u) 3, [10.sup.-3]          57.7             7
           BGS 5 (n,n,n,u) 5, [10.sup.-3]          57.7             6

TABLE 5.2
Results for the Stanford Berkeley matrix.

[alpha]    Solver                                    MB    Iterations

0.85       POWER                                    115            93
           GS                                       152            55
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          254            20
           BGS 2 (y,n,n,l) 3, [10.sup.-5]           254            44
           BGS 3 (y,y,n,u)                          357            42
           BGS 4 (n,n,n,u) 3, [10.sup.-3]           254            55
           BGS 5 (n,n,n,u) 3, [10.sup.-3]           254            55

0.9        POWER                                    115           143
           GS                                       152            78
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          254            27
           BGS 2 (y,n,n,l) 3, [10.sup.-5]           254            65
           BGS 3 (y,y,n,u)                          357            64
           BGS 4 (n,n,n,u) 3, [10.sup.-3]           254            78
           BGS 5 (n,n,n,u) 3, [10.sup.-3]           254            78

0.95       POWER                                    115           292
           GS                                       152           143
           BGS 1 (y,n,n,l) 5, [10.sup.-10]          254            31
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           320           119
           BGS 3 (y,y,n,u)                          357           128
           BGS 4 (n,n,n,u) 3, [10.sup.-5]           254           142
           BGS 5 (n,n,n,u) 5, [10.sup.-5]           254           137

0.97       POWER                                    115           490
           GS                                       152           239
           BGS 1 (y,n,n,l) 5, [10.sup.-10]          254            52
           BGS 2 (y,y,n,u) 5, [10.sup.-3]           320           186
           BGS 3 (y,y,n,l)                          357           209
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          254           169
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          254           173

0.99       POWER                                    115         1,454
           GS                                       152           719
           BGS 1 (y,n,n,l) 5, [10.sup.-10]          254           138
           BGS 2 (y,y,n,u) 3, [10.sup.-3]           320           524
           BGS 3 (y,y,n,l)                          357           559
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          254           454
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          254           411

[alpha]    Solver                              Residual     Setup (s)

0.85       POWER                                7.7e-11           3.1
           GS                                   6.3e-11           3.4
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      5.3e-11           4.0
           BGS 2 (y,n,n,l) 3, [10.sup.-5]       6.2e-11           4.1
           BGS 3 (y,y,n,u)                      7.2e-11           7.0
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       6.3e-11           3.7
           BGS 5 (n,n,n,u) 3, [10.sup.-3]       6.3e-11           3.7

0.9        POWER                                8.5e-11           3.4
           GS                                   7.1e-11           3.4
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      7.7e-11           4.2
           BGS 2 (y,n,n,l) 3, [10.sup.-5]       8.7e-11           4.2
           BGS 3 (y,y,n,u)                      7.5e-11           6.8
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       7.1e-11           3.6
           BGS 5 (n,n,n,u) 3, [10.sup.-3]       7.1e-11           3.8

0.95       POWER                                9.5e-11           3.0
           GS                                   8.5e-11           3.4
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      1.2e-10           4.2
           BGS 2 (y,y,n,l) 3, [10.sup.-3]       7.4e-11           4.6
           BGS 3 (y,y,n,u)                      8.5e-11           6.9
           BGS 4 (n,n,n,u) 3, [10.sup.-5]       8.6e-11           3.9
           BGS 5 (n,n,n,u) 5, [10.sup.-5]       9.3e-11           3.6

0.97       POWER                                9.6e-11           3.1
           GS                                   9.1e-11           3.4
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      1.5e-10           4.1
           BGS 2 (y,y,n,u) 5, [10.sup.-3]       9.0e-11           4.6
           BGS 3 (y,y,n,l)                      9.1e-11           6.7
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      9.2e-11           3.7
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      9.0e-11           3.8

0.99       POWER                                9.8e-11           3.1
           GS                                   9.7e-11           3.4
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      1.1e-10           4.1
           BGS 2 (y,y,n,u) 3, [10.sup.-3]       9.8e-11           4.8
           BGS 3 (y,y,n,l)                      9.7e-11           6.7
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      9.7e-11           3.9
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      9.5e-11           4.2

[alpha]    Solver                             Total (s)         Ratio

0.85       POWER                                    9.5
           GS                                       7.8
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          7.6            13
           BGS 2 (y,n,n,l) 3, [10.sup.-5]           8.7            15
           BGS 3 (y,y,n,u)                         11.7            57
           BGS 4 (n,n,n,u) 3, [10.sup.-3]           8.5             9
           BGS 5 (n,n,n,u) 3, [10.sup.-3]           8.5             9

0.9        POWER                                   13.2
           GS                                       9.7
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          9.2            12
           BGS 2 (y,n,n,l) 3, [10.sup.-5]          10.8            12
           BGS 3 (y,y,n,u)                         14.0            50
           BGS 4 (n,n,n,u) 3, [10.sup.-3]          10.4             3
           BGS 5 (n,n,n,u) 3, [10.sup.-3]          10.7             6

0.95       POWER                                   23.0
           GS                                      15.0
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         12.7            18
           BGS 2 (y,y,n,l) 3, [10.sup.-3]          16.5            23
           BGS 3 (y,y,n,u)                         21.3            57
           BGS 4 (n,n,n,u) 3, [10.sup.-5]          16.4            13
           BGS 5 (n,n,n,u) 5, [10.sup.-5]          15.8             9

0.97       POWER                                   36.5
           GS                                      22.5
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         17.7            15
           BGS 2 (y,y,n,u) 5, [10.sup.-3]          23.0            22
           BGS 3 (y,y,n,l)                         30.1            53
           BGS 4 (n,n,n,u) 3, [10.sup.-10]         22.4             9
           BGS 5 (n,n,n,u) 3, [10.sup.-10]         22.8            10

0.99       POWER                                  101.7
           GS                                      61.2
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         40.9            15
           BGS 2 (y,y,n,u) 3, [10.sup.-3]          56.8            25
           BGS 3 (y,y,n,l)                         69.3            53
           BGS 4 (n,n,n,u) 3, [10.sup.-10]         53.4            12
           BGS 5 (n,n,n,u) 3, [10.sup.-10]         49.6            16

TABLE 5.3
Results for the Eu2005 matrix.

[alpha]    Solver                                    MB    Iterations

0.85       POWER                                    256            90
           GS                                       340            48
           BGS 1 (y,n,n,l) 5, [10.sup.-10]          542            11
           BGS 2 (y,n,n,l) 5, [10.sup.-5]           542            43
           BGS 3 (y,y,n,l)                          746            41
           BGS 4 (n,n,n,u) 3, [10.sup.-5]           542            44
           BGS 5 (n,n,n,u) 5, [10.sup.-5]           542            44

0.9        POWER                                    256           137
           GS                                       340            71
           BGS 1 (y,n,n,l) 5, [10.sup.-10]          542            15
           BGS 2 (y,n,n,l) 3, [10.sup.-3]           542            72
           BGS 3 (y,y,n,l)                          746            63
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          542            52
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          542            53

0.95       POWER                                    256           269
           GS                                       340           140
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          542            47
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           663           132
           BGS 3 (y,y,n,l)                          746           127
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          542            96
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          542            98

0.97       POWER                                    256           434
           GS                                       340           228
           BGS 1 (y,n,n,u) 3, [10.sup.-10]          542            85
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           663           214
           BGS 3 (y,y,n,l)                          746           210
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          542           168
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          542           171

0.99       POWER                                    256         1,258
           GS                                       340           634
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          542           267
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           663           590
           BGS 3 (y,y,n,l)                          746           594
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          542           502
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          542           511

[alpha]    Solver                              Residual     Setup (s)

0.85       POWER                                7.9e-11           7.6
           GS                                   4.5e-11           8.6
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      5.4e-11           9.5
           BGS 2 (y,n,n,l) 5, [10.sup.-5]       7.1e-11           9.6
           BGS 3 (y,y,n,l)                      7.1e-11          19.1
           BGS 4 (n,n,n,u) 3, [10.sup.-5]       5.3e-11           8.8
           BGS 5 (n,n,n,u) 5, [10.sup.-5]       5.6e-11           9.0

0.9        POWER                                8.1e-11           7.4
           GS                                   4.0e-11           8.3
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      5.8e-11           9.6
           BGS 2 (y,n,n,l) 3, [10.sup.-3]       1.8e-11           9.6
           BGS 3 (y,y,n,l)                      7.1e-11          18.9
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      7.0e-11           8.6
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      8.0e-11           8.8

0.95       POWER                                9.4e-11           7.7
           GS                                   1.7e-11           8.5
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      8.2e-11           9.6
           BGS 2 (y,y,n,l) 3, [10.sup.-3]       6.7e-11          10.5
           BGS 3 (y,y,n,l)                      8.7e-11          18.6
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      9.0e-11           8.9
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      8.1e-11           9.1

0.97       POWER                                9.6e-11           7.3
           GS                                   2.3e-11           8.6
           BGS 1 (y,n,n,u) 3, [10.sup.-10]      5.6e-11           9.8
           BGS 2 (y,y,n,l) 3, [10.sup.-3]       7.7e-11          10.5
           BGS 3 (y,y,n,l)                      9.1e-11          18.5
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      9.2e-11           8.9
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      9.3e-11           9.9

0.99       POWER                                9.9e-11           7.4
           GS                                   4.8e-11           8.3
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      7.0e-11           9.9
           BGS 2 (y,y,n,l) 3, [10.sup.-3]       8.3e-11          10.5
           BGS 3 (y,y,n,l)                      9.5e-11          18.9
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      9.6e-11           8.9
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      9.7e-11           8.8

[alpha]    Solver                             Total (s)         Ratio

0.85       POWER                                   20.3
           GS                                      16.0
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         15.5            13
           BGS 2 (y,n,n,l) 5, [10.sup.-5]          18.0            14
           BGS 3 (y,y,n,l)                         29.5            81
           BGS 4 (n,n,n,u) 3, [10.sup.-5]          16.0             9
           BGS 5 (n,n,n,u) 5, [10.sup.-5]          16.3            10

0.9        POWER                                   26.7
           GS                                      19.2
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         18.5            16
           BGS 2 (y,n,n,l) 3, [10.sup.-3]          22.2            16
           BGS 3 (y,y,n,l)                         34.9            82
           BGS 4 (n,n,n,u) 3, [10.sup.-10]         18.8             9
           BGS 5 (n,n,n,u) 3, [10.sup.-10]         19.1            10

0.95       POWER                                   45.2
           GS                                      29.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         29.1            14
           BGS 2 (y,y,n,l) 3, [10.sup.-3]          33.6            20
           BGS 3 (y,y,n,l)                         50.8            78
           BGS 4 (n,n,n,u) 3, [10.sup.-10]         27.2             9
           BGS 5 (n,n,n,u) 3, [10.sup.-10]         27.8            10

0.97       POWER                                   67.5
           GS                                      43.6
           BGS 1 (y,n,n,u) 3, [10.sup.-10]         43.0            18
           BGS 2 (y,y,n,l) 3, [10.sup.-3]          47.9            23
           BGS 3 (y,y,n,l)                         71.8            81
           BGS 4 (n,n,n,u) 3, [10.sup.-10]         40.1            12
           BGS 5 (n,n,n,u) 3, [10.sup.-10]         42.0            19

0.99       POWER                                  182.5
           GS                                     105.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]        115.1            18
           BGS 2 (y,y,n,l) 3, [10.sup.-3]         113.3            22
           BGS 3 (y,y,n,l)                        169.5            83
           BGS 4 (n,n,n,u) 3, [10.sup.-10]        100.9            11
           BGS 5 (n,n,n,u) 3, [10.sup.-10]        102.8            10

TABLE 5.4
Results for the WebGoogle matrix.

[alpha]    Solver                                    MB    Iterations

0.85       POWER                                     97            92
           GS                                       127            42
           BGS 1 (y,n,n,l) 5, [10.sup.-10]          225            11
           BGS 2 (y,n,n,l) 3, [10.sup.-3]           225            42
           BGS 3 (y,y,n,l)                          324            41
           BGS 4 (y,n,n,u) 3, [10.sup.-3]           225            42
           BGS 5 (n,n,n,u) 3, [10.sup.-3]           225            42

0.9        POWER                                     97           142
           GS                                       127            63
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          225            24
           BGS 2 (y,y,n,u) 3, [10.sup.-3]           295            60
           BGS 3 (y,y,n,l)                          324            61
           BGS 4 (n,n,n,u) 3, [10.sup.-5]           225            63
           BGS 5 (n,n,n,u) 3, [10.sup.-3]           225            63

0.95       POWER                                     97           291
           GS                                       127           121
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          225            46
           BGS 2 (y,y,n,u) 3, [10.sup.-3]           295           118
           BGS 3 (y,y,n,u)                          324           127
           BGS 4 (n,n,n,u) 3, [10.sup.-3]           225           121
           BGS 5 (n,n,n,u) 3, [10.sup.-3]           225           121

0.97       POWER                                     97           489
           GS                                       127           195
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          225            74
           BGS 2 (y,y,n,u) 3, [10.sup.-3]           295           191
           BGS 3 (y,y,n,u)                          324           204
           BGS 4 (n,n,n,u) 5, [10.sup.-3]           225           195
           BGS 5 (n,n,n,u) 5, [10.sup.-3]           225           195

0.99       POWER                                     97          1481
           GS                                       127           528
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          225           198
           BGS 2 (y,y,n,l) 5, [10.sup.-3]           295           532
           BGS 3 (y,y,n,u)                          324           553
           BGS 4 (n,n,n,u) 3, [10.sup.-5]           225           527
           BGS 5 (n,n,n,u) 3, [10.sup.-3]           225           528

[alpha]    Solver                              Residual     Setup (s)

0.85       POWER                                8.0e-11           3.2
           GS                                   5.7e-11           3.9
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      4.0e-11           8.0
           BGS 2 (y,n,n,l) 3, [10.sup.-3]       7.4e-11           8.0
           BGS 3 (y,y,n,l)                      6.8e-11           9.8
           BGS 4 (y,n,n,u) 3, [10.sup.-3]       5.7e-11           5.3
           BGS 5 (n,n,n,u) 3, [10.sup.-3]       5.7e-11           5.3

0.9        POWER                                8.4e-11           3.4
           GS                                   5.8e-11           3.8
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      7.1e-11           8.0
           BGS 2 (y,y,n,u) 3, [10.sup.-3]       7.5e-11          10.1
           BGS 3 (y,y,n,l)                      7.9e-11          10.0
           BGS 4 (n,n,n,u) 3, [10.sup.-5]       5.8e-11           5.2
           BGS 5 (n,n,n,u) 3, [10.sup.-3]       5.8e-11           5.3

0.95       POWER                                9.1e-11           3.3
           GS                                   7.7e-11           3.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      8.2e-11           8.0
           BGS 2 (y,y,n,u) 3, [10.sup.-3]       8.4e-11          10.3
           BGS 3 (y,y,n,u)                      8.1e-11          10.0
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       7.7e-11           5.2
           BGS 5 (n,n,n,u) 3, [10.sup.-3]       7.7e-11           5.3

0.97       POWER                                9.6e-11           3.3
           GS                                   8.2e-11           3.8
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      8.7e-11           8.1
           BGS 2 (y,y,n,u) 3, [10.sup.-3]       9.1e-11          10.1
           BGS 3 (y,y,n,u)                      8.9e-11           9.9
           BGS 4 (n,n,n,u) 5, [10.sup.-3]       8.2e-11           5.4
           BGS 5 (n,n,n,u) 5, [10.sup.-3]       8.2e-11           5.3

0.99       POWER                                9.8e-11           3.2
           GS                                   9.8e-11           3.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      9.8e-11           8.0
           BGS 2 (y,y,n,l) 5, [10.sup.-3]       9.8e-11           9.8
           BGS 3 (y,y,n,u)                      9.2e-11           9.9
           BGS 4 (n,n,n,u) 3, [10.sup.-5]       9.8e-11           5.3
           BGS 5 (n,n,n,u) 3, [10.sup.-3]       9.8e-11           5.3

[alpha]    Solver                             Total (s)         Ratio

0.85       POWER                                   32.8
           GS                                      19.4
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         18.6            15
           BGS 2 (y,n,n,l) 3, [10.sup.-3]          21.2            15
           BGS 3 (y,y,n,l)                         17.5            21
           BGS 4 (y,n,n,u) 3, [10.sup.-3]          20.3             7
           BGS 5 (n,n,n,u) 3, [10.sup.-3]          20.2             7

0.9        POWER                                   48.7
           GS                                      26.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         24.5            14
           BGS 2 (y,y,n,u) 3, [10.sup.-3]          26.9            21
           BGS 3 (y,y,n,l)                         21.4            21
           BGS 4 (n,n,n,u) 3, [10.sup.-5]          27.7             6
           BGS 5 (n,n,n,u) 3, [10.sup.-3]          27.8             6

0.95       POWER                                   96.2
           GS                                      48.4
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         41.3            15
           BGS 2 (y,y,n,u) 3, [10.sup.-3]          43.2            22
           BGS 3 (y,y,n,u)                         33.7            21
           BGS 4 (n,n,n,u) 3, [10.sup.-3]          48.5             6
           BGS 5 (n,n,n,u) 3, [10.sup.-3]          48.5             6

0.97       POWER                                  159.3
           GS                                      75.7
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         60.9            15
           BGS 2 (y,y,n,u) 3, [10.sup.-3]          63.4            21
           BGS 3 (y,y,n,u)                         48.0            21
           BGS 4 (n,n,n,u) 5, [10.sup.-3]          75.0             7
           BGS 5 (n,n,n,u) 5, [10.sup.-3]          75.0             6

0.99       POWER                                  472.9
           GS                                     197.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]        138.5            15
           BGS 2 (y,y,n,l) 5, [10.sup.-3]         158.1            21
           BGS 3 (y,y,n,u)                        112.9            21
           BGS 4 (n,n,n,u) 3, [10.sup.-5]         193.4             7
           BGS 5 (n,n,n,u) 3, [10.sup.-3]         193.5             7

TABLE 5.5
Results for the In2004 matrix.

[alpha]    Solver                                    MB    Iterations

0.85       POWER                                    252           100
           GS                                       332            57
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          551            21
           BGS 2 (y,y,n,l) 3, [10.sup.-3]           690            44
           BGS 3 (y,y,n,u)                          771            44
           BGS 4 (n,n,n,u) 3, [10.sup.-5]           551            52
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          551            40

0.9        POWER                                    252           151
           GS                                       332            84
           BGS 1 (y,n,n,l) 3, [10.sup.-10]          551            30
           BGS 2 (y,y,n,u) 5, [10.sup.-3]           690            63
           BGS 3 (y,y,n,u)                          771            65
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          551            58
           BGS 5 8n,n,n,u) 5, [10.sup.-5]           551            58

0.95       POWER                                    252           313
           GS                                       332           159
           BGS 1 (y,n,n,l) 5, [10.sup.-10]          551            40
           BGS 2 (y,y,n,u) 5, [10.sup.-3]           690           124
           BGS 3 (y,y,n,l)                          771           128
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          551           110
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          551           110

0.97       POWER                                    252           526
           GS                                       332           253
           BGS 1 (y,n,n,l) 5, [10.sup.-10]          551            54
           BGS 2 (y,n,n,l) 3, [10.sup.-10]          551           145
           BGS 3 (y,y,n,l)                          771           207
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          551           173
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          551           173

0.99       POWER                                    252         1,379
           GS                                       332           757
           BGS 1 (y,n,n,u) 3, [10.sup.-10]          551           222
           BGS 2 (y,n,n,l) 3, [10.sup.-10]          551           387
           BGS 3 (y,y,n,l)                          771           556
           BGS 4 (n,n,n,u) 3, [10.sup.-10]          551           449
           BGS 5 (n,n,n,u) 3, [10.sup.-10]          551           448

[alpha]    Solver                              Residual     Setup (s)

0.85       POWER                                3.8e-10           6.9
           GS                                   6.4e-11           8.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      4.9e-11           9.3
           BGS 2 (y,y,n,l) 3, [10.sup.-3]       6.9e-11           9.7
           BGS 3 (y,y,n,u)                      2.0e-11          29.7
           BGS 4 (n,n,n,u) 3, [10.sup.-5]       7.5e-11           8.1
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      1.4e-11           8.0

0.9        POWER                                4.8e-10           7.1
           GS                                   7.2e-11           7.9
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      6.5e-11           9.4
           BGS 2 (y,y,n,u) 5, [10.sup.-3]       7.3e-11          10.1
           BGS 3 (y,y,n,u)                      3.2e-11          30.0
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      1.8e-11           8.7
           BGS 5 8n,n,n,u) 5, [10.sup.-5]       1.8e-11           8.3

0.95       POWER                                2.6e-10           6.9
           GS                                   6.1e-11           7.7
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      6.9e-11           9.2
           BGS 2 (y,y,n,u) 5, [10.sup.-3]       8.5e-11          10.1
           BGS 3 (y,y,n,l)                      8.9e-11          30.6
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      2.1e-11           8.3
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      2.3e-11           8.1

0.97       POWER                                1.3e-10           6.9
           GS                                   8.7e-11           7.8
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      9.0e-11           9.0
           BGS 2 (y,n,n,l) 3, [10.sup.-10]      9.4e-11           9.1
           BGS 3 (y,y,n,l)                      9.2e-11          30.2
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      3.1e-11           8.3
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      3.3e-11           8.4

0.99       POWER                                1.8e-10           7.0
           GS                                   9.9e-11           7.9
           BGS 1 (y,n,n,u) 3, [10.sup.-10]      9.2e-11           9.2
           BGS 2 (y,n,n,l) 3, [10.sup.-10]      9.7e-11           9.4
           BGS 3 (y,y,n,l)                      9.3e-11          30.2
           BGS 4 (n,n,n,u) 3, [10.sup.-10]      9.7e-11           8.6
           BGS 5 (n,n,n,u) 3, [10.sup.-10]      9.8e-11           8.4

[alpha]    Solver                             Total (s)         Ratio

0.85       POWER                                   21.3
           GS                                      18.3
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         17.0            17
           BGS 2 (y,y,n,l) 3, [10.sup.-3]          18.8            19
           BGS 3 (y,y,n,u)                         39.8           158
           BGS 4 (n,n,n,u) 3, [10.sup.-5]          17.5             8
           BGS 5 (n,n,n,u) 3, [10.sup.-10]         17.3             8

0.9        POWER                                   28.8
           GS                                      21.8
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         20.2            16
           BGS 2 (y,y,n,u) 5, [10.sup.-3]          23.3            21
           BGS 3 (y,y,n,u)                         44.8           159
           BGS 4 (n,n,n,u) 3, [10.sup.-10]         22.0            11
           BGS 5 8n,n,n,u) 5, [10.sup.-5]          21.8             8

0.95       POWER                                   51.6
           GS                                      34.0
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         28.4            16
           BGS 2 (y,y,n,u) 5, [10.sup.-3]          36.0            22
           BGS 3 (y,y,n,l)                         60.0           166
           BGS 4 (n,n,n,u) 3, [10.sup.-10]         33.3            10
           BGS 5 (n,n,n,u) 3, [10.sup.-10]         33.3             8

0.97       POWER                                   82.1
           GS                                      49.7
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         36.1            15
           BGS 2 (y,n,n,l) 3, [10.sup.-10]         51.9            15
           BGS 3 (y,y,n,l)                         77.5           163
           BGS 4 (n,n,n,u) 3, [10.sup.-10]         47.4            10
           BGS 5 (n,n,n,u) 3, [10.sup.-10]         47.7            10

0.99       POWER                                  204.9
           GS                                     133.0
           BGS 1 (y,n,n,u) 3, [10.sup.-10]         91.9            15
           BGS 2 (y,n,n,l) 3, [10.sup.-10]        126.4            17
           BGS 3 (y,y,n,l)                        157.3           162
           BGS 4 (n,n,n,u) 3, [10.sup.-10]        108.0            11
           BGS 5 (n,n,n,u) 3, [10.sup.-10]        108.4            10

TABLE 5.6
Results for the WebBase matrix.

[alpha]    Solver                                    MB    Iterations

0.85       POWER                                    625            96
           GS                                       826            44
           BGS 1 (y,n,n,l) 3, [10.sup.-10]        1,341            18
           BGS 2 (y,n,n,u) 5, [10.sup.-3]         1,341            46
           BGS 3 (y,y,n,l)                        1,858            42
           BGS 4 (n,n,n,u) 3, [10.sup.-5]         1,341            44
           BGS 5 (n,n,n,u) 5, [10.sup.-3]         1,341            45

0.9        POWER                                    625           147
           GS                                       826            65
           BGS 1 (y,n,n,l) 5, [10.sup.-10]        1,341            17
           BGS 2 (y,n,n,u) 5, [10.sup.-3]         1,341            68
           BGS 3 (y,y,n,l)                        1,858            62
           BGS 4 (n,n,n,u) 3, [10.sup.-3]         1,341            66
           BGS 5 (n,n,n,u) 5, [10.sup.-3]         1,341            66

0.95       POWER                                    625           300
           GS                                       826           126
           BGS 1 (y,n,n,l) 3, [10.sup.-10]        1,341            44
           BGS 2 (y,y,n,u) 5, [10.sup.-3]         1,657           122
           BGS 3 (y,y,n,l)                        1,858           121
           BGS 4 (n,n,n,u) 3, [10.sup.-3]         1,341           127
           BGS 5 (n,n,n,u) 3, [10.sup.-3]         1,341           127

0.97       POWER                                    625           503
           GS                                       826           205
           BGS 1 (y,n,n,l) 3, [10.sup.-10]        1,341            72
           BGS 2 (y,y,n,u) 5, [10.sup.-3]         1,657           197
           BGS 3 (y,y,n,l)                        1,858           196
           BGS 4 (n,n,n,u) 3, [10.sup.-5]         1,341           206
           BGS 5 8n,n,n,u) 5, [10.sup.-3]         1,341           206

0.99       POWER                                    625         1,511
           GS                                       826           583
           BGS 1 (y,n,n,l) 3, [10.sup.-10]        1,341           221
           BGS 2 (y,y,n,u) 3, [10.sup.-3]         1,657           559
           BGS 3 (y,y,n,l)                        1,858           563
           BGS 4 (n,n,n,u) 3, [10.sup.-3]         1,341           587
           BGS 5 (n,n,n,u) 3, [10.sup.-5]         1,341           583

[alpha]    Solver                              Residual     Setup (s)

0.85       POWER                                7.2e-11          21.3
           GS                                   7.4e-11          20.5
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      6.8e-11          24.3
           BGS 2 (y,n,n,u) 5, [10.sup.-3]       6.7e-11          23.7
           BGS 3 (y,y,n,l)                      6.1e-11          38.1
           BGS 4 (n,n,n,u) 3, [10.sup.-5]       6.3e-11          20.9
           BGS 5 (n,n,n,u) 5, [10.sup.-3]       6.2e-11          21.0

0.9        POWER                                8.3e-11          18.6
           GS                                   7.9e-11          21.3
           BGS 1 (y,n,n,l) 5, [10.sup.-10]      7.9e-11          22.8
           BGS 2 (y,n,n,u) 5, [10.sup.-3]       7.0e-11          22.8
           BGS 3 (y,y,n,l)                      7.5e-11          37.4
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       7.4e-11          21.6
           BGS 5 (n,n,n,u) 5, [10.sup.-3]       7.9e-11          20.8

0.95       POWER                                9.4e-11          17.7
           GS                                   8.3e-11          20.5
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      9.0e-11          24.2
           BGS 2 (y,y,n,u) 5, [10.sup.-3]       9.0e-11          26.2
           BGS 3 (y,y,n,l)                      7.4e-11          39.3
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       8.3e-11          20.6
           BGS 5 (n,n,n,u) 3, [10.sup.-3]       8.7e-11          21.4

0.97       POWER                                9.5e-11          18.5
           GS                                   9.2e-11          21.0
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      9.2e-11          23.1
           BGS 2 (y,y,n,u) 5, [10.sup.-3]       9.3e-11          26.1
           BGS 3 (y,y,n,l)                      8.6e-11          38.0
           BGS 4 (n,n,n,u) 3, [10.sup.-5]       9.2e-11          20.9
           BGS 5 8n,n,n,u) 5, [10.sup.-3]       9.4e-11          20.6

0.99       POWER                                9.9e-11          18.1
           GS                                   9.7e-11          21.4
           BGS 1 (y,n,n,l) 3, [10.sup.-10]      9.8e-11          23.1
           BGS 2 (y,y,n,u) 3, [10.sup.-3]       9.7e-11          25.5
           BGS 3 (y,y,n,l)                      9.8e-11          37.4
           BGS 4 (n,n,n,u) 3, [10.sup.-3]       9.8e-11          22.1
           BGS 5 (n,n,n,u) 3, [10.sup.-5]       9.8e-11          20.8

[alpha]    Solver                             Total (s)         Ratio

0.85       POWER                                   53.4
           GS                                      37.1
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         39.8             9
           BGS 2 (y,n,n,u) 5, [10.sup.-3]          45.0             7
           BGS 3 (y,y,n,l)                         63.8            50
           BGS 4 (n,n,n,u) 3, [10.sup.-5]          39.8             0
           BGS 5 (n,n,n,u) 5, [10.sup.-3]          40.2             0

0.9        POWER                                   67.8
           GS                                      45.9
           BGS 1 (y,n,n,l) 5, [10.sup.-10]         44.1            13
           BGS 2 (y,n,n,u) 5, [10.sup.-3]          54.0            13
           BGS 3 (y,y,n,l)                         75.2            56
           BGS 4 (n,n,n,u) 3, [10.sup.-3]          49.4             9
           BGS 5 (n,n,n,u) 5, [10.sup.-3]          49.1             7

0.95       POWER                                  119.4
           GS                                      69.1
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         64.4            19
           BGS 2 (y,y,n,u) 5, [10.sup.-3]          82.0            25
           BGS 3 (y,y,n,l)                        112.9            64
           BGS 4 (n,n,n,u) 3, [10.sup.-3]          73.6             9
           BGS 5 (n,n,n,u) 3, [10.sup.-3]          76.5            11

0.97       POWER                                  185.8
           GS                                      98.7
           BGS 1 (y,n,n,l) 3, [10.sup.-10]         88.3            14
           BGS 2 (y,y,n,u) 5, [10.sup.-3]         115.9            23
           BGS 3 (y,y,n,l)                        156.8            59
           BGS 4 (n,n,n,u) 3, [10.sup.-5]         110.9             7
           BGS 5 8n,n,n,u) 5, [10.sup.-3]         108.3             6

0.99       POWER                                  522.1
           GS                                     242.0
           BGS 1 (y,n,n,l) 3, [10.sup.-10]        222.5            15
           BGS 2 (y,y,n,u) 3, [10.sup.-3]         279.8            22
           BGS 3 (y,y,n,l)                        378.3            58
           BGS 4 (n,n,n,u) 3, [10.sup.-3]         266.5            12
           BGS 5 (n,n,n,u) 3, [10.sup.-5]         265.0             8
COPYRIGHT 2011 Institute of Computational Mathematics
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Dayar, Tugrul; Noyan, Gokce N.
Publication:Electronic Transactions on Numerical Analysis
Article Type:Report
Geographic Code:7TURK
Date:Jan 1, 2011
Words:20752
Previous Article:Error estimates for general fidelities.
Next Article:Fields of values and inclusion regions for matrix pencils.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters