-
-
Notifications
You must be signed in to change notification settings - Fork 209
Iterative Solver Comparison
Anders Peterson edited this page May 21, 2022
·
5 revisions
There is an updated version of this at https://www.ojalgo.org/2022/05/iterative-solver-comparison/
Via Google you may find linAlg34.pdf that I believe originates from the University of Oxford. Among other things it describes the Jacobi and Gauss-Seidel methods, and contain a detailed comparison of the two. That comparison is in part reproduced here using the built in ojAlgo iterative solvers.
Further the Gauss-Seidel solver is compared to the Conjugate Gradient solver using a small example from Hestenes and Steifel's original paper from 1952.
import org.ojalgo.OjAlgoUtils;
import org.ojalgo.matrix.store.PrimitiveDenseStore;
import org.ojalgo.matrix.task.iterative.ConjugateGradientSolver;
import org.ojalgo.matrix.task.iterative.GaussSeidelSolver;
import org.ojalgo.matrix.task.iterative.JacobiSolver;
import org.ojalgo.netio.BasicLogger;
import org.ojalgo.type.context.NumberContext;
/**
* IterativeSolverComparison
*
* @author apete
*/
public class IterativeSolverComparison {
public static void main(final String[] args) {
BasicLogger.debug();
BasicLogger.debug(IterativeSolverComparison.class.getSimpleName());
BasicLogger.debug(OjAlgoUtils.getTitle());
BasicLogger.debug(OjAlgoUtils.getDate());
BasicLogger.debug();
BasicLogger.debug("Simple 3x3 example from linAlg34.pdf");
final PrimitiveDenseStore tmpBody = PrimitiveDenseStore.FACTORY.rows(new double[][] { { 4, 2, 3 }, { 3, -5, 2 }, { -2, 3, 8 } });
final PrimitiveDenseStore tmpRHS = PrimitiveDenseStore.FACTORY.columns(new double[] { 8, -14, 27 });
final JacobiSolver tmpJacobi = new JacobiSolver();
// In the example the Jacobi solver is shown to converge to a sufficiently accurate solution within 50 iterations
tmpJacobi.configurator().debug(BasicLogger.DEBUG).iterations(50).accuracy(NumberContext.getMath(6));
BasicLogger.debug();
BasicLogger.debug("Jacobi");
tmpJacobi.solve(tmpBody, tmpRHS);
final GaussSeidelSolver tmpGaussSeidel = new GaussSeidelSolver();
// Same problem and requirements/limits, but using a Gauss Seidel solver.
tmpGaussSeidel.configurator().debug(BasicLogger.DEBUG).iterations(50).accuracy(NumberContext.getMath(6));
BasicLogger.debug();
BasicLogger.debug("Gauss-Seidel");
tmpGaussSeidel.solve(tmpBody, tmpRHS);
tmpGaussSeidel.setRelaxationFactor(0.9);
// The Gauss Seidel solver again, but this time (under) relaxed by a factor 0.9
BasicLogger.debug();
BasicLogger.debug("Gauss-Seidel (relaxed x 0.9)");
tmpGaussSeidel.solve(tmpBody, tmpRHS);
BasicLogger.debug();
BasicLogger.debug("4x4 example from Hestenes and Steifel's original paper from 1952");
BasicLogger.debug("\tMethods of Conjugate Gradients for Solving Linear Systems");
final PrimitiveDenseStore tmpBody1952 = PrimitiveDenseStore.FACTORY
.rows(new double[][] { { 1, 2, -1, 1 }, { 2, 5, 0, 2 }, { -1, 0, 6, 0 }, { 1, 2, 0, 3 } });
final PrimitiveDenseStore tmpRHS1952 = PrimitiveDenseStore.FACTORY.columns(new double[] { 3, 9, 5, 6 });
final ConjugateGradientSolver tmpConjugateGradient = new ConjugateGradientSolver();
// Theoretically a conjugate gradient solver should be able to solve a 4x4 system within 4 iterations
tmpConjugateGradient.configurator().debug(BasicLogger.DEBUG).iterations(50).accuracy(NumberContext.getMath(6));
BasicLogger.debug();
BasicLogger.debug("Conjugate Gradient");
tmpConjugateGradient.solve(tmpBody1952, tmpRHS1952);
tmpGaussSeidel.setRelaxationFactor(1.75);
// The same problem using the Gauss Seidel solver (over) relaxed by a factor 1.75
BasicLogger.debug();
BasicLogger.debug("Gauss-Seidel (relaxed x 1.75)");
tmpGaussSeidel.solve(tmpBody1952, tmpRHS1952);
}
}
IterativeSolverComparison
ojAlgo
2016-02-25
Simple 3x3 example from linAlg34.pdf
Jacobi
1: [2.0, 2.8, 3.375]
2: [-1.9312500000000004, 5.35, 2.825]
3: [-2.79375, 2.771249999999999, 0.8859374999999998]
4: [-0.05007812499999931, 1.4781249999999997, 1.6373437500000003]
5: [0.032929687499999805, 3.4248906250000006, 2.8081835937500004]
6: [-1.8185830078125007, 3.94303125, 2.0988984374999995]
7: [-1.5456894531249998, 2.5484095703125, 1.441717529296875]
8: [-0.355492932128906, 2.44927333984375, 2.0329240478515627]
9: [-0.7493297058105468, 3.3998738598632814, 2.367649264526367]
10: [-1.475673878326416, 3.297461882324219, 1.9127148760986326]
11: [-1.083267098236084, 2.6796816234436034, 1.769533324546814]
12: [-0.6669908051319122, 2.8578530708770753, 2.0993026166496276]
13: [-1.0034034979257587, 3.239526563580703, 2.1365573971381187]
14: [-1.2221813296439403, 3.0525808600997926, 1.9093266641757967]
15: [-0.9582854281817437, 2.830421867883955, 1.924736845051593]
16: [-0.8587635677306722, 2.994923481111591, 2.0740204424980813]
17: [-1.0529770724293563, 3.1143500363608294, 2.0372128026504854]
18: [-1.085084620168279, 2.9830988776025804, 1.9438744682573499]
19: [-0.9494552899943025, 2.9264990152019728, 1.985066765856963]
20: [-0.9520495819937087, 3.024353532346204, 2.0401990468006845]
21: [-1.0423260512736154, 3.0448498695240485, 2.0028550298717462]
22: [-1.024566207165834, 2.9757463811845293, 1.9725997861100781]
23: [-0.9673230301748232, 2.9743001901445307, 2.0029535552643427]
24: [-0.9893652615205222, 3.0207876040008435, 2.017806671152095]
25: [-1.023748805364493, 3.0135035115485245, 1.9948633331195533]
26: [-1.0028992556139271, 2.9836960500291254, 1.9889989818281801]
27: [-0.9835972613856978, 2.993860039362916, 2.005389167335596]
28: [-1.0009718951831552, 3.0119973101028195, 2.006403169892482]
29: [-1.010801032470771, 3.001978130847099, 1.9952580349156541]
30: [-0.9974325916102902, 2.9916225944837986, 1.9965579428146452]
31: [-0.9932297543528832, 3.0001636221596844, 2.003783379166003]
32: [-1.0029193454543441, 3.005575499054671, 2.0016312031018977]
33: [-1.0040111518537587, 2.998900873968152, 1.9971793514909124]
34: [-0.9973349506022604, 2.99646504948411, 1.9994093842985032]
35: [-0.9977895629659326, 3.001362783358045, 2.001991868792894]
36: [-1.0021752932736927, 3.0021230097375975, 2.00004156549925]
37: [-1.0010926789932362, 2.9987114502354846, 1.9986600480299779]
38: [-0.9983507611402258, 2.998808411816049, 2.0002100364133844]
39: [-0.9995617332180631, 3.0010735578812184, 2.0008591552839254]
40: [-1.001181145403553, 3.0006066221827323, 1.9997069824900273]
41: [-1.0000835479588868, 2.9991741057538785, 1.9994772303305872]
42: [-0.9991949756248797, 2.999740763356903, 2.000288823352574]
43: [-1.0000869991928818, 3.000598543966101, 2.0002984698349415]
44: [-1.0005231243592565, 3.0000671884182473, 1.9997537962144918]
45: [-0.9998489413699925, 2.999587643870243, 1.9998440232533432]
46: [-0.9996768393751287, 3.0000282444793425, 2.0001923982061607]
47: [-1.000158420894292, 3.000270855657387, 2.0000701984764646]
48: [-1.0001880766860423, 2.9999330268540105, 1.9998588239049067]
49: [-0.9998606313556853, 2.999830683550337, 1.9999780957582356]
50: [-0.9998989135938452, 3.000074859489883, 2.000098335829702]
Gauss Seidel
1: [2.0, 4.0, 2.375]
2: [-1.78125, 2.68125, 1.92421875]
3: [-0.7837890625000001, 3.0994140624999997, 2.0167724609374997]
4: [-1.0622863769531248, 2.969337158203125, 1.9959269714355465]
5: [-0.9816138076782226, 3.009402503967285, 2.0010706090927126]
6: [-1.005504208803177, 2.9971257183551785, 1.9997018034160137]
7: [-0.9983392117395995, 3.000877194322646, 2.0000862491941076]
8: [-1.0005032840569037, 2.999732529243501, 1.9999744805194615]
9: [-0.9998471250113465, 3.000081517200977, 2.000007649796797]
10: [-1.000046495948086, 2.9999751623498674, 1.9999976901317784]
11: [-0.9999858487737676, 3.000007566788451, 2.000000700260889]
Gauss Seidel (relaxed x 0.9)
1: [1.8, 3.492, 2.2639500000000004]
2: [-1.1195662500000003, 3.079656225, 1.9726086178125002]
3: [-1.0293127432734377, 2.9822758435448433, 1.996647397348342]
4: [-0.9926923971326541, 3.0009667529482544, 2.0009826712599517]
5: [-1.0003675816404476, 3.0002519428625662, 1.999930530540778]
6: [-1.0001032405672245, 2.999944435374636, 1.9999885769875128]
7: [-0.9999776094418797, 3.0000024221543526, 2.0000030780972344]
8: [-1.00000092862928, 3.0000008488706285, 1.9999998123742984]
4x4 example from Hestenes and Steifel's original paper from 1952
Methods of Conjugate Gradients for Solving Linear Systems
Conjugate Gradient
1: [1.4709600948241803, 0.8825760568945081, 0.4086000263400501, 0.9806400632161202]
2: [1.0194610191440532, 0.9496580786326301, 1.0000478393811107, 1.0639090141692322]
3: [1.0500178202676569, 0.9816297762195523, 1.0084050025447466, 0.9955359134386417]
4: [0.99999999999985, 0.9999999999999687, 1.0000000000000204, 0.9999999999999588]
Gauss Seidel (relaxed x 1.75)
1: [5.25, -0.525, 2.9895833333333335, 1.0499999999999998]
2: [6.544270833333334, -1.7722395833333335, 1.1248914930555558, 0.9626215277777778]
3: [6.828607855902778, -0.9746808810763886, 2.6063420048466432, -0.06819303385416708]
4: [8.220363509566694, -1.8255086721914768, 1.90118285332197, 0.8856928457001104]
5: [7.251115233833403, -1.1766341515298517, 2.147354803209932, -0.02134701055974042]
6: [7.725111279076356, -1.3601593743142422, 2.100974687323155, 0.5965479484918804]
7: [6.849471143747312, -1.0420938338317531, 1.8803647347672665, 0.27284034424886977]
8: [6.5733927440078475, -0.8607927864058869, 1.9652993325935058, 0.46514889194897147]
9: [5.957993465542653, -0.7006050604397224, 1.7221069280048111, 0.4930147133180666]
10: [5.384533988083842, -0.43883029565154386, 1.737242217187512, 0.5012294835560102]
11: [4.9105278275726505, -0.3091073960514043, 1.5876389534847224, 0.6202286166422512]
12: [4.341948104974751, -0.09169315809334852, 1.5340056488374272, 0.6090008273919469]
13: [3.9332234121252463, 0.039212900907975995, 1.4550192585751263, 0.7031206713236741]
14: [3.4786598154181902, 0.19334398359971294, 1.3816780022322939, 0.7178732899803022]
15: [3.125959442278347, 0.3143090997191606, 1.3338130023236305, 0.7714247415133832]
16: [2.7896280256921098, 0.42153123816678434, 1.2716150890841424, 0.8023619843499834]
17: [2.50361258043195, 0.5196693760275586, 1.2348423524795453, 0.8315069011200562]
18: [2.2592847884586886, 0.5966937852742098, 1.1911596322741254, 0.8623109480724779]
19: [2.0425933575491326, 0.6690466471092149, 1.1607200050795696, 0.8811995754145634]
20: [1.8655524688696596, 0.7254885836691328, 1.1319127996106402, 0.9044580306511211]
21: [1.7096714511849482, 0.775992924962902, 1.1080529068876297, 0.9190230513637206]
22: [1.5825734214079734, 0.8168877753376375, 1.0888775677449367, 0.9345291444286481]
23: [1.4740724610657931, 0.851313044650663, 1.0716129586688203, 0.9460289872976945]
24: [1.3846219478228052, 0.8800595619276526, 1.0584716824467029, 0.9560459677144983]
25: [1.3105700731674697, 0.9033240999368831, 1.0467291761721513, 0.9645881982734051]
26: [1.2491848066681124, 0.9228658215882755, 1.0376320198157527, 0.9711909222188926]
27: [1.1993529402344576, 0.9384699300914481, 1.029920592706569, 0.9771026747590404]
28: [1.158271895912264, 0.9513853529615008, 1.0237221917778168, 0.9815648095268148]
29: [1.1252227616398025, 0.9617096854622419, 1.0187316616449134, 0.9854518155257223]
30: [1.0983387603608858, 0.9700643327826931, 1.014633392204907, 0.9884718065653831]
31: [1.0768035398590765, 0.9767590079158585, 1.011425988305217, 0.9909585709229993]
32: [1.0595587978190686, 0.9820685859436585, 1.008801824801649, 0.9929584228123591]
33: [1.0458168043141518, 0.9863059015536983, 1.006761865990391, 0.9945311618948273]
34: [1.0349704734936782, 0.9896194290627721, 1.005128321942863, 0.995812851801]
35: [1.0264062159082994, 0.9922320808064112, 1.0038555715161068, 0.9967993075952624]
36: [1.0197315171078147, 0.9942543621030374, 1.0028633471860326, 0.997593711870451]
37: [1.014532956610776, 0.9958205604858629, 1.0020912686219516, 0.9982031708407022]
38: [1.0105324919585836, 0.9970196156761028, 1.0015035253547897, 0.9986807832715127]
39: [1.0074717748104365, 0.9979284975855589, 1.0010516236369518, 0.9990476300571256]
40: [1.0051534161074123, 0.9986128944956543, 1.0007143619702814, 0.9993264078162355]
41: [1.0034187269542323, 0.9991187347889317, 1.0004613572172734, 0.9995390794941011]
42: [1.0021343690386169, 0.9994895349353989, 1.0002765063899746, 0.9996961843489321]
43: [1.0012014145189654, 0.9997545295909225, 1.0001430327755507, 0.9998134187461618]
44: [1.000534910093978, 0.99994027261871, 1.000048740862414, 0.9998975869970633]
45: [1.0000723825283953, 1.0000658168681467, 0.9999845559239713, 0.9999578002644673]
46: [0.9997621764693225, 1.000146653635237, 0.9999422178605739, 0.9999992842867683]
47: [0.9995652136788389, 1.0001948611976472, 0.9999165239275641, 1.0000268240750128]
48: [0.9994510502910703, 1.0002193420455068, 0.9999024967225558, 1.0000442035541917]