I. S. Duff, A. M. Erisman, and J. K. Reid, Direct Methods for Sparse Matrices, 1989.

W. H. Joseph and . Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Trans. Math. Software, vol.11, issue.2, pp.141-153, 1985.

G. Esmond, P. Ng, and . Raghavan, Performance of greedy ordering heuristics for sparse Cholesky factorization, SIAM J. Matrix Anal. Appl, vol.20, issue.4, pp.902-914, 1999.

E. Rothberg and S. C. Eisenstat, Node Selection Strategies for Bottom-Up Sparse Matrix Ordering, SIAM Journal on Matrix Analysis and Applications, vol.19, issue.3, pp.682-695, 1998.
DOI : 10.1137/S0895479896302692

W. F. Tinney and J. W. Walker, Direct solutions of sparse network equations by optimally ordered triangular factorization, Proc. IEEE, pp.1801-1809, 1967.
DOI : 10.1109/PROC.1967.6011

O. Wing, J. F. Huang-]-l, O. N. Costa, G. Oliveira-jr, F. A. Travieso et al., SCAP -a sparse matrix circuit analysis program References Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications, Proceedings - IEEE International Symposium on Circuits and Systems, pp.213-215, 1975.

R. Glantz, H. Meyerhenke, and C. Schulz, Tree-based coarsening and partitioning of complex networks, Proc. 13th Intl. Symp. on Experimental Algorithms, pp.364-375, 2014.

L. Grady and E. L. Schwartz, Isoperimetric graph partitioning for image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, issue.3, pp.469-475, 2006.
DOI : 10.1109/TPAMI.2006.57

B. Hendrickson and T. G. Kolda, Graph partitioning models for parallel computing, Parallel Computing, vol.26, issue.12
DOI : 10.1016/S0167-8191(00)00048-X

R. Kannan, S. Vempala, and A. Vetta, On clusterings, Journal of the ACM, vol.51, issue.3
DOI : 10.1145/990308.990313

H. Meyerhenke, P. Sanders, and C. Schulz, Partitioning Complex Networks via Size-Constrained Clustering, Proc. 13th Intl. Symp. on Experimental Algorithms, pp.351-363, 2014.
DOI : 10.1007/978-3-319-07959-2_30

U. N. Raghavan, R. Albert, and S. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Physical Review E, vol.76, issue.3
DOI : 10.1103/PhysRevE.76.036106

I. Safro, P. Sanders, and C. Schulz, Advanced coarsening schemes for graph partitioning, Proc. 11th Int. Symp. on Experimental Algorithms, pp.369-380, 2012.

P. Sanders and C. Schulz, Think Locally, Act Globally: Highly Balanced Graph Partitioning, Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), pp.164-175, 2013.
DOI : 10.1007/978-3-642-38527-8_16

¨. U. and C. Aykanat, Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication, IEEE Transactions on Parallel and Distributed Systems, vol.10, issue.7, pp.673-693, 1999.

B. Hendrickson and T. G. Kolda, Graph partitioning models for parallel computing, Parallel Computing, vol.26, issue.12, pp.1519-1534, 2000.
DOI : 10.1016/S0167-8191(00)00048-X

¨. U. and C. Aykanat, A fine-grain hypergraph model for 2D decomposition of sparse matrices, Proceedings of 15th International Parallel and Distributed Processing Symposium (IPDPS), 2001.

B. Vastenhouw and R. H. Bisseling, A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication, SIAM Review, vol.47, issue.1, pp.67-95, 2005.
DOI : 10.1137/S0036144502409019

K. Devine, E. Boman, R. Heaphy, R. Bisseling, and ¨. U. , Parallel hypergraph partitioning for scientific computing, Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, 2006.
DOI : 10.1109/IPDPS.2006.1639359

K. Kaya, B. Uçar, and U. V. , On analysis of partitioning models and metrics in parallel sparse matrixvector multiplication, Proc. of the 10th Int'l Conf. on Parallel Processing and Applied Mathematics (PPAM), 2013.
URL : https://hal.archives-ouvertes.fr/hal-00821523

B. Uçar and C. Aykanat, Encapsulating Multiple Communication-Cost Metrics in Partitioning Sparse Rectangular Matrices for Parallel Matrix-Vector Multiplies, SIAM Journal on Scientific Computing, vol.25, issue.6, pp.1837-1859, 2004.
DOI : 10.1137/S1064827502410463

R. H. Bisseling and W. Meesen, Communication balancing in parallel sparse matrix-vector multiplication, Electronic Transactions on Numerical Analysis, vol.21, pp.47-65, 2005.

¨. U. , M. Deveci, K. Kaya, and B. Uçar, UMPa: A multi-objective, multi-level partitioner for communication minimization, in: 10th DIMACS Implementation Challenge Workshop: Graph Partitioning and Graph Clustering, Contemporary Mathematics, pp.53-66, 2012.

A. Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2008.
DOI : 10.1137/1.9780898717761

U. Naumann, The Art of Differentiating Computer Programs: An Introduction to Algorithmic Differentiation, 2012.
DOI : 10.1137/1.9781611972078

R. M. Gower and M. P. Mello, A New Framework for The Computation of Hessians. Optimization Methods and Software, pp.251-273, 2012.

T. S. Munson and P. D. Hovland, The feasNewt benchmark, IEEE International. 2005 Proceedings of the IEEE Workload Characterization Symposium, 2005., 2005.
DOI : 10.1109/IISWC.2005.1526011

L. Luksan, C. Matonoha, and J. Vlcek, Sparse Test Problems for Unconstrained Optimization, ICS AS CR, 2010.

C. Ashcraft and J. W. Liu, Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement, SIAM Journal on Matrix Analysis and Applications, vol.19, issue.2
DOI : 10.1137/S0895479896308433

A. Pothen and C. Fan, Computing the block triangular form of a sparse matrix, ACM Transactions on Mathematical Software, vol.16, issue.4
DOI : 10.1145/98267.98287

C. M. Fiduccia and R. M. Mattheyses, A linear-time heuristic for improving network partitions, 19th Conference on Design Automation, pp.175-181, 1982.

A. George, Nested Dissection of a Regular Finite Element Mesh, SIAM Journal on Numerical Analysis, vol.10, issue.2, pp.345-363, 1973.
DOI : 10.1137/0710032

B. Hendrickson and R. Leland, A multi-level algorithm for partitioning graphs, Supercomputing Proceedings of the IEEE/ACM SC95 Conference, pp.28-28, 1995.

G. Karypis, V. Kumar, and V. Kumar, Parallel multilevel k-way partitioning scheme for irregular graphs, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM) , Supercomputing '96, pp.96-129, 1998.
DOI : 10.1145/369028.369103

R. J. Lipton, D. J. Rose, and R. E. Tarjan, Generalized Nested Dissection, SIAM Journal on Numerical Analysis, vol.16, issue.2, 1979.
DOI : 10.1137/0716027

F. Pellegrini and J. Roman, Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs, High-Performance Computing and Networking, pp.493-498, 1996.
DOI : 10.1007/3-540-61142-8_588

W. Fong and E. Darve, The black-box fast multipole method, Journal of Computational Physics, vol.228, issue.23, pp.8712-8725, 2009.
DOI : 10.1016/j.jcp.2009.08.031

L. Ying and G. Biros, Denis Zorin, A kernel-independent adaptive fast multipole algorithm in two and three dimensions, Journal of Computational Physics, pp.591-625, 2004.

K. Nabors, F. T. Korsmeyer, F. T. Leighton, and J. Preconditioned, Preconditioned, Adaptive, Multipole-Accelerated Iterative Methods for Three-Dimensional First-Kind Integral Equations of Potential Theory, SIAM Journal on Scientific Computing, vol.15, issue.3, pp.713-735
DOI : 10.1137/0915046

]. A. Aggarwal, A. K. Chandra, and M. Snir, Communication complexity of PRAMs, Theor. Comput. Sci, vol.7, issue.1, pp.3-5, 1990.

G. Ballard, A. Buluç, J. Demmel, L. Grigori, B. Lipshitz et al., Communication optimal parallel multiplication of sparse random matrices, Proceedings of the 25th ACM symposium on Parallelism in algorithms and architectures, SPAA '13
DOI : 10.1145/2486159.2486196
URL : https://hal.archives-ouvertes.fr/hal-00870940

G. Ballard, J. Demmel, O. Holtz, B. Lipshitz, and O. Schwartz, Brief announcement, Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures, SPAA '12, pp.7-7, 2012.
DOI : 10.1145/2312005.2312021

G. Ballard, J. Demmel, O. Holtz, B. Lipshitz, and O. Schwartz, Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication, Lecture Notes in Computer Science, vol.7659, pp.13-36, 2012.
DOI : 10.1007/978-3-642-34862-4_2

G. Ballard, J. Demmel, O. Holtz, and O. Schwartz, Minimizing Communication in Numerical Linear Algebra, SIAM Journal on Matrix Analysis and Applications, vol.32, issue.3, pp.866-901, 2011.
DOI : 10.1137/090769156

G. Ballard, J. Demmel, O. Holtz, and O. Schwartz, Graph expansion and communication costs of fast matrix multiplication, Journal of the ACM, vol.5, issue.2, pp.9-10, 2012.

P. Bay and G. Bilardi, Deterministic on-line routing on area-universal networks, Proceedings of the 31st Annual Symposium on the Foundations of Computer Science (FOCS), pp.2-9
DOI : 10.1145/210346.210417

G. Bilardi, M. Scquizzato, and F. Silvestri, A Lower Bound Technique for Communication on BSP with Application to the FFT, Euro-Par 2012 Parallel Processing, pp.676-687, 2012.
DOI : 10.1007/978-3-642-32820-6_67

B. Bollobás and I. Leader, Edge-isoperimetric inequalities in the grid, Combinatorica, vol.1, issue.1 4

M. Christ, J. Demmel, N. Knight, T. Scanlon, and K. Yelick, Communication lower bounds and optimal algorithms for programs that reference arrays -part 1, 2013.

M. Driscoll, E. Georganas, P. Koanantakool, E. Solomonik, and K. Yelick, A Communication-Optimal N-Body Algorithm for Direct Interactions, 2013 IEEE 27th International Symposium on Parallel and Distributed Processing
DOI : 10.1109/IPDPS.2013.108

M. T. Goodrich, Communication-Efficient Parallel Sorting, SIAM Journal on Computing, vol.29, issue.2
DOI : 10.1137/S0097539795294141

R. I. Greenberg and C. E. Leiserson, Randomized routing on fat-tress, 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pp.241-249, 1985.
DOI : 10.1109/SFCS.1985.46

J. W. Hong and H. T. Kung, The red-blue pebble game, Proc. 14th STOC, 1981.

D. Irony, S. Toledo, and A. Tiskin, Communication lower bounds for distributed-memory matrix multiplication, Journal of Parallel and Distributed Computing, vol.64, issue.9
DOI : 10.1016/j.jpdc.2004.03.021

N. Knight, E. Carson, and J. Demmel, Exploiting Data Sparsity in Parallel Matrix Powers Computations, Proceedings of PPAM '13,L e c t u r eN o t e si nC o m p u t e r Science, p.2013
DOI : 10.1007/978-3-642-55224-3_2

C. E. Leiserson, Fat-trees: Universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, vol.34, issue.10
DOI : 10.1109/TC.1985.6312192

J. P. Michael, M. Penner, and V. K. Prasanna, Optimizing graph algorithms for improved cache performance, Proc

M. Scquizzato and F. Silvestri, Communication lower bounds for distributed-memory computations. arXiv preprint

E. Solomonik, E. Carson, N. Knight, and J. Demmel, Tradeoffsb e t w e e ns y n c h r o n i z a t i o n ,c o m m u n i c a t i o n ,a n d work in parallel linear algebra computations, 2013.

E. Solomonik and J. Demmel, Communication-Optimal Parallel 2.5D Matrix Multiplication and LU Factorization Algorithms, Euro-Par'11: Proceedings of the 17th International European Conference on Parallel and Distributed Computing.S p r i n g e r
DOI : 10.1007/978-3-642-23397-5_10

]. A. Buluç, J. T. Fineman, M. Frigo, J. R. Gilbert, and C. E. Leiserson, Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks, Proc. 21st Symp. on Parallelism in Algorithms and Arch

A. Buluç and J. R. Gilbert, The Combinatorial BLAS: design, implementation, and applications, International Journal of High Performance Computing Applications, vol.25, issue.4
DOI : 10.1177/1094342011403516

T. Davis, Direct Methods for Sparse Linear Systems, 2006.
DOI : 10.1137/1.9780898718881

F. G. Gustavson, Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition, ACM Transactions on Mathematical Software, vol.4, issue.3
DOI : 10.1145/355791.355796

J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos, Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication, Proc. 9th Principles and Practice of Knowledge Disc. in Databases
DOI : 10.1007/11564126_17

C. Pheatt, Intel threading building blocks, J. Comput. Sci. Coll, vol.23, issue.4, pp.298-298, 2008.

H. Samet, The quadtree and related hierarchical data structures Computing Surveys

Y. Shapira, Matrix-based Multigrid: Theory and Applications, 2003.

J. Shun and G. E. Blelloch, Ligra, ACM SIGPLAN Notices, vol.48, issue.8, pp.135-146, 2013.
DOI : 10.1145/2517327.2442530

R. A. Van-de-geijn and J. Watts, Summa: Scalable universal matrix multiplication algorithm. Concurrency: Practice and Experience

P. Ghysels and W. Vanroose, Hiding global synchronization latency in the preconditioned Conjugate Gradient algorithm, Parallel Computing, vol.40, issue.7, 2013.
DOI : 10.1016/j.parco.2013.06.001

O. Selvitopi, M. Ozdal, and C. Aykanat, A novel method for scaling iterative solvers: Avoiding latency overhead of parallel sparse-matrix vector multiplies, Parallel and Distributed Systems, IEEE Transactions, pp.99-2014

D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, Graph partitioning and graph clustering, 2013.
DOI : 10.1090/conm/588

C. Bekas, E. Kokiopoulou, and Y. Saad, An estimator for the diagonal of a matrix, Applied Numerical Mathematics, vol.57, issue.11-12, pp.11-121214, 2007.
DOI : 10.1016/j.apnum.2007.01.003

M. Hutchinson, A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines Communications in Statistics-Simulation and Computation References [1] J. Alstott, E. Bullmore, and D. Plenz. powerlaw: a python package for analysis of heavy-tailed distributions, PLOS ONE, vol.18, issue.91, pp.1059-1076, 1989.

M. Bastian, S. Heymann, and M. Jacomy, Gephi: an open source software for exploring and manipulating networks, In ICWSM, issue.2, pp.3-6

S. Behnel, R. Bradshaw, C. Citro, L. Dalcin, D. S. Seljebotn et al., Cython: The Best of Both Worlds, Computing in Science & Engineering, vol.13, issue.2, pp.3-4
DOI : 10.1109/MCSE.2010.118

U. Brandes and T. Erlebach, Network analysis: methodological foundations,v o l u m e3 4 1 8 . S p r i n g e r
DOI : 10.1007/b106453

M. Newman, Networks: an introduction.O x f o r dU n i v e r s i t y Press, 2010.
DOI : 10.1093/acprof:oso/9780199206650.001.0001

F. Perez, B. E. Granger, and C. Obispo, An open source framework for interactive, collaborative and reproducible scientific computing and education, 2013.

C. L. Staudt and H. Meyerhenke, Engineering high-performance community detection heuristics for massive graphs. arXiv preprint arXiv, pp.1304-4453

E. G. Boman, K. D. Devine, and S. Rajamanickam, Scalable matrix computations on large scale-free graphs using 2D graph partitioning, Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis on, SC '13, pp.1-50, 2013.
DOI : 10.1145/2503210.2503293

C. G. Baker, Anasazi software for the numerical solution of large-scale eigenvalue problems, ACM Transactions on Mathematical Software, vol.36, issue.3, pp.13-14, 2009.
DOI : 10.1145/1527286.1527287

B. A. Miller, N. T. Bliss, P. J. Wolfe, and M. S. Beard, Detection theory for graphs, pp.10-30, 2013.

M. E. Newman, Finding community structure in networks using the eigenvectors of matrices, Physical Review E, vol.74, issue.3, 2006.
DOI : 10.1103/PhysRevE.74.036104

A. Yoo, A. H. Baker, R. Pearce, and V. E. Henson, A scalable eigensolver for large scale-free graphs using 2D graph partitioning, Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis on, SC '11, pp.1-63, 2011.
DOI : 10.1145/2063384.2063469

U. Brandes, Faster Algorithm for, Betweenness Centrality J. Math. Sociol

L. C. Freeman, A Set of Measures of Centrality Based on Betweenness, Sociometry, vol.40, issue.1
DOI : 10.2307/3033543

A. J. Macula and L. J. Popyack, A group testing method for finding patterns in data, Discrete Applied Mathematics, vol.144, issue.1-2, pp.149-157, 2004.
DOI : 10.1016/j.dam.2003.07.009

A. J. Macula, Probabilistic nonadaptive group testing in the presence of errors and DNA library screening, Annals of Combinatorics, vol.80, issue.1, pp.61-69, 1998.
DOI : 10.1007/BF01609876

V. V. Ufimtsev, A Scalable Group Testing Based Algorithm for Finding d-highest Betweenness Centrality Vertices, Large Scale Networks,Poster, International Conference for High Performance Computing, Networking, Storage and Analysis

P. A. Prasad and R. Ramalakshmi, Performance analysis of CDS-based hybrid path in WSN for condition monitoring, 2013 IEEE CONFERENCE ON INFORMATION AND COMMUNICATION TECHNOLOGIES, pp.798-802, 2013.
DOI : 10.1109/CICT.2013.6558203

R. Asgarnezhad and J. A. Torkestani, A survey on backbone formation algorithms for Wireless Sensor Networks: (A New Classification), 2011 Australasian Telecommunication Networks and Applications Conference (ATNAC), pp.47-54, 2011.
DOI : 10.1109/ATNAC.2011.6096632

D. Mahjoub and D. W. Matula, Constructing efficient rotating backbones in wireless sensor networks using graph coloring, Computer Communications, vol.35, issue.9, pp.1086-1097, 2012.
DOI : 10.1016/j.comcom.2012.02.013

D. Mahjoub and D. W. Matula, Employing (1-epsilon) Dominating Set Partitions as Backbones in Wireless Sensor Networks, ALENEX, pp.98-111, 2010.

D. W. Matula and L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM, vol.30, issue.3, pp.417-427, 1983.
DOI : 10.1145/2402.322385

D. W. Matula, A min-max theorem for graphs with application to graph coloring, SIAM Review, issue.10, pp.481-482, 1968.

E. G. Coffman, M. Elphick, and A. Shoshani, System Deadlocks, ACM Computing Surveys, vol.3, issue.2, pp.67-78, 1971.
DOI : 10.1145/356586.356588

I. S. Duff and J. K. Reid, The Multifrontal Solution of Unsymmetric Sets of Linear Equations, SIAM Journal on Scientific and Statistical Computing, vol.5, issue.3, pp.633-641, 1984.
DOI : 10.1137/0905045

A. N. Habermann-]-e, D. Boman, B. Chen, S. Hendrickson, and . Toledo, Prevention of system deadlocks References Maximum-weight-basis preconditioners, [2] K. Gremban. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems, p.373, 1969.

S. Kaczmarz, Angenäherte auflösung von systemen linearer gleichungen, Bulletin International de lAcademie Polonaise des Sciences et des Lettres, pp.355-357, 1937.

J. A. Kelner, L. Orecchia, A. Sidford, and Z. A. Zhu, A simple, combinatorial algorithm for solving SDD systems in nearly-linear time, Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC '13, pp.9-10, 2013.
DOI : 10.1145/2488608.2488724

I. Koutis, G. L. Miller, and R. Peng, Approaching optimality for solving sdd systems. CoRR,a b s, 2010.

O. E. Livne and A. Brandt, Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver, SIAM Journal on Scientific Computing, vol.34, issue.4
DOI : 10.1137/110843563

D. A. Spielman, Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices, Proceedings of the International Congress of Mathematicians 2010 (ICM 2010), pp.2698-2722, 2010.
DOI : 10.1142/9789814324359_0164

D. A. Spielman and S. Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , STOC '04, pp.81-90, 2004.
DOI : 10.1145/1007352.1007372

S. Toledo, An algebraic view of the new randomized Kaczmarz linear solver, Presented at the Simons Institute for the Theory of Computing, 2013.

B. Wilkinson and M. Allen, Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, 2004.

A. H. Gebremedhin, F. Manne, and A. Pothen, What Color Is Your Jacobian? Graph Coloring for Computing Derivatives, SIAM Review, vol.47, issue.4
DOI : 10.1137/S0036144504444711

D. Goldfarb and P. L. Toint, Optimal estimation of Jacobian and Hessian matrices that arise in finite difference calculations, Mathematics of Computation, vol.43, issue.167
DOI : 10.1090/S0025-5718-1984-0744925-5

M. Lülfesmann and K. Kawarabayashi, Sub-exponential graph coloring algorithm for stencil-based Jacobian computations, Journal of Computational Science, vol.5, issue.1, pp.1-1
DOI : 10.1016/j.jocs.2013.06.002

D. K. Melgaard and R. F. Sincovec, General Software for Two-Dimensional Nonlinear Partial Differential Equations, ACM Transactions on Mathematical Software, vol.7, issue.1
DOI : 10.1145/355934.355941

G. N. Newsam and J. D. , Estimation of Sparse Jacobian Matrices, SIAM Journal on Algebraic Discrete Methods, vol.4, issue.3
DOI : 10.1137/0604041

H. N. Gabow and R. E. Tarjan, Faster Scaling Algorithms for Network Problems, SIAM Journal on Computing, vol.18, issue.5
DOI : 10.1137/0218069

G. D. Morales, A. Gionis, and M. Sozio, Social content matching in Mapreduce, 37th Int. Conf. on Very Large Data Bases (VLDB 2011), pp.4-6
URL : https://hal.archives-ouvertes.fr/hal-00816075

J. Mestre, Greedy in Approximation Algorithms, Algorithms -ESA 2006, pp.528-539, 2006.
DOI : 10.1007/11841036_48

B. C. Huang and T. Jebara, Fast b-matching via sufficient selection belief propagation, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, ser. JMLR Proceedings, pp.361-369, 2011.

G. Georgiadis and M. Papatriantafilou, Overlays with Preferences: Distributed, Adaptive Approximation Algorithms for Matching with Preference Lists, Algorithms, vol.6, issue.4
DOI : 10.3390/a6040824

. Fremuth-paeger, D. Christian, and . Jungnickel, Balanced network flows. I. A unifying framework for design and analysis of matching algorithms, Networks, vol.14, issue.1, pp.1-28, 1999.
DOI : 10.1002/(SICI)1097-0037(199901)33:1<1::AID-NET1>3.0.CO;2-M

F. Manne and M. Halappanavar, New Effective Multithreaded Matching Algorithms, 2014 IEEE 28th International Parallel and Distributed Processing Symposium
DOI : 10.1109/IPDPS.2014.61

]. R. References and . Bellman, On a routing problem, Quart. Appl. Math, vol.16, issue.1, pp.87-90, 1958.

P. Briggs and L. Torczon, An efficient representation for sparse sets, ACM Letters on Programming Languages and Systems, vol.2, issue.1-4, pp.59-69, 1993.
DOI : 10.1145/176454.176484

V. Chakaravarthy, F. Checconi, F. Petrini, and Y. Sabharwal, Scalable single source shortest path algorithms for massively parallel systems, Proc. IEEE Int'l. Parallel and Distributed Proc. Symp. (IPDPS), 2014.

R. Dial, Algorithm 360: shortest-path forest with topological ordering [H], Communications of the ACM, vol.12, issue.11, pp.632-633, 1969.
DOI : 10.1145/363269.363610

E. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, vol.4, issue.1, pp.269-271, 1959.
DOI : 10.1007/BF01386390

N. Edmonds, T. Hoefler, and A. Lumsdaine, A space-efficient parallel algorithm for computing betweenness centrality in distributed memory, 2010 International Conference on High Performance Computing, 2010.
DOI : 10.1109/HIPC.2010.5713180

N. Edmonds, J. Willcock, and A. Lumsdaine, Expressing graph algorithms using generalized active messages, Proc. ACM Int'l. Conf. on Supercomputing (ICS), 2013.

M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala et al., Optimistic parallelism requires abstractions, Proc. ACM SIGPLAN Conf. on Programming language design and implementation (PLDI), 2007.

K. Madduri, D. A. Bader, J. Berry, and J. R. Crobak, An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances, Proc. Workshop on Algorithm Engineering and Experiments (ALENEX), 2007.
DOI : 10.1137/1.9781611972870.3

U. Meyer and P. Sanders, ??-stepping: a parallelizable shortest path algorithm, Journal of Algorithms, vol.49, issue.1, pp.114-152, 2003.
DOI : 10.1016/S0196-6774(03)00076-2
URL : http://dx.doi.org/10.1016/s0196-6774(03)00076-2

D. Nguyen, A. Lenharth, and K. Pingali, A lightweight infrastructure for graph analytics, Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP '13, 2013.
DOI : 10.1145/2517349.2522739

T. Panitanarak and K. Madduri, Performance analysis of single-source shortest path algorithms on distributed-memory systems, 2014.

R. Armstrong, D. Hensgen, and T. Kidd, The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions, Proceedings Seventh Heterogeneous Computing Workshop (HCW'98), pp.79-87, 1998.
DOI : 10.1109/HCW.1998.666547

T. D. Braun, H. J. Siegel, N. Beck, L. L. Bölöni, M. Maheswaran et al., A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems, Journal of Parallel and Distributed Computing, vol.61, issue.6, p.1
DOI : 10.1006/jpdc.2000.1714

H. Oscar, C. E. Ibarra, and . Kim, Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors, Journal of the ACM, vol.24, issue.2, pp.280-289, 1977.

M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund, Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems, Journal of Parallel and Distributed Computing, vol.59, issue.2
DOI : 10.1006/jpdc.1999.1581

E. Tabak, B. B. Cambazoglu, and C. Aykanat, Improving the Performance of IndependentTask Assignment Heuristics MinMin,MaxMin and Sufferage, IEEE Transactions on Parallel and Distributed Systems, vol.25, issue.5, pp.1244-1256, 2014.
DOI : 10.1109/TPDS.2013.107

M. Gardner, Mathematics, Magic and Mystery, 1956.

J. E. Simpson, Langford sequences: perfect and hooked, Discrete Mathematics, vol.44, issue.1, pp.97-104, 1983.
DOI : 10.1016/0012-365X(83)90008-0

C. Jaillet, M. Krajecki, and A. Bui, Parallel tree search for combinatorial problems: a comparative study between openmp and mpi, Studia Informatica Universalis, vol.4, issue.2, pp.151-190, 2005.

L. Steffenel, O. Flauzac, A. S. Charao, P. P. Barcelos, B. Stein et al., PER-MARE: Adaptive Deployment of MapReduce over Pervasive Grids, 2013 Eighth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, 2013.
DOI : 10.1109/3PGCIC.2013.10
URL : https://hal.archives-ouvertes.fr/hal-00903718

G. J. Woeginger, ) does not take into account the memory footprint of ghost cells added in phase (2) For 2D meshes the size of the edge cut between two parts grows as O(n References A review of machine scheduling : Complexity, algorithms and approximability, Handbook of Combinatorial Optimization, 1998.

]. B. Hen98 and . Hendrickson, Graph partitioning and parallel solvers: Has the emperor no clothes? Lecture Notes in Computer Science, 1998.

A. H. Gebremedhin, F. Manne, and A. Pothen, What Color Is Your Jacobian? Graph Coloring for Computing Derivatives, SIAM Review, vol.47, issue.4, pp.629-705, 2005.
DOI : 10.1137/S0036144504444711

D. Goldfarb and P. L. Toint, Optimal estimation of Jacobian and Hessian matrices that arise in finite difference calculations, Mathematics of Computation, vol.43, issue.167, pp.69-88, 1984.
DOI : 10.1090/S0025-5718-1984-0744925-5

S. W. Sloan, An algorithm for profile and wavefront reduction of sparse matrices, International Journal for Numerical Methods in Engineering, vol.2, issue.2, pp.239-251, 1986.
DOI : 10.1002/nme.1620230208

J. Camata, A. Rossa, A. Valli, L. Catabriga, G. Carey et al., Reordering and incomplete preconditioning in serial and parallel adaptive mesh refinement and coarsening flow solutions, International Journal for Numerical Methods in Fluids, vol.10, issue.3, pp.802-823, 2012.
DOI : 10.1002/fld.2614

M. Benzi, ¨. U. , and C. Aykanat, Preconditioning Techniques for Large Linear Systems: A Survey, Journal of Computational Physics, vol.182, issue.2, pp.418-477, 1999.
DOI : 10.1006/jcph.2002.7176

H. Coullon, M. Le, and S. Limet, Parallelization of Shallow-Water Equations with the Algorithmic Skeleton Library SkelGIS, ICCS, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00832660

H. Coullon and S. Limet, Algorithmic skeleton library for scientific simulations: SkelGIS, HPCS, pp.429-436, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00845891

B. Uçar and C. Aykanat, Partitioning sparse matrices for parallel preconditioned iterative methods

B. Vastenhouw and R. H. Bisseling, A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication, SIAM Review, vol.47, issue.1, pp.67-95, 2005.
DOI : 10.1137/S0036144502409019
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.5652

E. Agullo, A. Buttari, A. Guermouche, and F. Lopez, Multifrontal QR Factorization for Multicore Architectures over Runtime Systems, Euro-Par 2013 Parallel Processing, pp.521-532, 2013.
DOI : 10.1007/978-3-642-40047-6_53
URL : https://hal.archives-ouvertes.fr/hal-01220611

P. Amestoy, X. Li, and E. Ng, Diagonal Markowitz Scheme with Local Symmetrization, SIAM Journal on Matrix Analysis and Applications, vol.29, issue.1, pp.228-244, 2007.
DOI : 10.1137/050637315
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.119.5689

P. R. Amestoy, I. S. Duff, and J. Excellent, Multifrontal parallel distributed symmetric and unsymmetric solvers, Computer methods in applied mechanics and engineering, pp.501-520, 2000.

S. C. Eisenstat and J. W. Liu, The Theory of Elimination Trees for Sparse Unsymmetric Matrices, SIAM Journal on Matrix Analysis and Applications, vol.26, issue.3, pp.686-705, 2005.
DOI : 10.1137/S089547980240563X

S. C. Eisenstat and J. W. Liu, Algorithmic Aspects of Elimination Trees for Sparse Unsymmetric Matrices, SIAM Journal on Matrix Analysis and Applications, vol.29, issue.4, pp.1363-1381, 2008.
DOI : 10.1137/050643581

H. Gruber, Digraph complexity measures and applications in formal language theory, Discrete Mathematics & Theoretical Computer Science, vol.14, pp.189-204, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00990597

A. Guermouche, J. Excellent, and G. Utard, Impact of reordering on the memory of a multifrontal solver, Parallel Computing, vol.29, issue.9, pp.1191-1218, 2003.
DOI : 10.1016/S0167-8191(03)00099-1
URL : https://hal.archives-ouvertes.fr/hal-00807378

J. Hogg, J. Reid, and J. Scott, Design of a Multicore Sparse Cholesky Factorization Using DAGs, SIAM Journal on Scientific Computing, vol.32, issue.6, pp.3627-3649, 2010.
DOI : 10.1137/090757216

G. Karypis and V. Kumar, A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, 1998.

K. Kaya and B. Uçar, Constructing Elimination Trees for Sparse Unsymmetric Matrices, SIAM Journal on Matrix Analysis and Applications, vol.34, issue.2, pp.345-354, 2013.
DOI : 10.1137/110825443
URL : https://hal.archives-ouvertes.fr/inria-00567970

J. W. Liu, Computational models and task scheduling for parallel sparse Cholesky factorization, Parallel Computing, vol.3, issue.4, pp.327-342, 1986.
DOI : 10.1016/0167-8191(86)90014-1

J. W. Liu, A graph partitioning algorithm by node separators, ACM Transactions on Mathematical Software, vol.15, issue.3, pp.198-219, 1989.
DOI : 10.1145/66888.66890

A. Pothen, The complexity of optimal elimination trees, 1988.

R. Schreiber, A New Implementation of Sparse Gaussian Elimination, ACM Transactions on Mathematical Software, vol.8, issue.3, pp.256-276, 1982.
DOI : 10.1145/356004.356006

Y. Deng, A. Barros, and A. Grall, Calculation of failure level based on inverse first passage problem, 2014 Reliability and Maintainability Symposium, 2014.
DOI : 10.1109/RAMS.2014.6798459

X. Chen, L. Cheng, J. Chadam, and D. Saunders, Existence and uniqueness of solutions to the inverse boundary crossing problem for diffusions, The Annals of Applied Probability, vol.21, issue.5, pp.1663-1693, 2011.
DOI : 10.1214/10-AAP714

G. Peskir, On Integral Equations Arising in the First-Passage Problem for Brownian Motion, Journal of Integral Equations and Applications, vol.14, issue.4, pp.397-423, 2002.
DOI : 10.1216/jiea/1181074930

C. Zucca and L. Sacerdote, On the inverse first-passage-time problem for a Wiener process, The Annals of Applied Probability, vol.19, issue.4, pp.1319-1346, 2009.
DOI : 10.1214/08-AAP571

I. Charles-delaunay, U. Of, . Of, and . Troyes, BP 2060 -10010 TROYES CEDEX,FRANCE. E-mail address: yingjun.deng@utt.fr Key words and phrases. inverse first passage time