lukefleed/ShfitedPowGMRES
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
Methods for solving PageRank with multiple damping factors
58 commits 1 branch 0 tags 4.9 MiB
  • Python 96.4%
  • TeX 3.6%
Find a file
Exact
Luca Lombardo 3ff9aac145 stats
2023-01-20 11:05:00 +01:00
testing Changed norm 1 with norm 2. This does not change the fact that the shifted-GMRES doesn't work 2023-01-04 00:24:55 +01:00
tex typos and fixes, closing the project 2023-01-18 16:30:15 +01:00
.gitattributes stats 2023-01-20 11:05:00 +01:00
.gitignore small fixes 2023-01-04 00:23:11 +01:00
algo.py Changed norm 1 with norm 2. This does not change the fact that the shifted-GMRES doesn't work 2023-01-04 00:24:55 +01:00
main.py now the program prints the number of mv for each iteration in the standard power method 2023-01-04 00:23:52 +01:00
README.md final version 2022-12-27 17:39:17 +01:00
requirements.txt small fixes 2022-12-24 16:15:27 +01:00

README.md

Documentation

Report of the project: view / download

This repository contains the code of my attempt to replicate the results obtained in [1]. The scripts are all written in python and are heavily build around the libraries SciPy and NumPy. To install all the required packages with pip run the following command in terminal

pip install -r requirements.txt

At the moment, the standard and shifted power method to compute the PageRank with multiple damping factors are fully implemented (as described in [1]). To run the program we need to execute the main.py file. It takes as input two arguments:

  • --dataset: the options are BerkStan and Stanford. This commands selects the web-graph to run the algorithms on.
  • --algo: the options are power, shifted, both. If you choose the last option, it will first run the standard power method and then the shifted one.

Here an example of what's described above.

./main.py --dataset Stanford --algo both

Under development

In the testing/ folder there are two python notebook that contains the attempt on replicating the results obtained in [1] for the shifted GMRES method. The implementation of the Arnoldi process is fully working. On the other hand, there are several problems on the shifted GMRES algorithm that I can't figure out.

References

[1] Zhao-Li Shen, Meng Su, Bruno Carpentieri, and Chun Wen. Shifted power-gmres method accelerated by extrapolation for solving pagerank with multiple damping factors. Applied Mathematics and Computation, 420:126799, 2022